# 144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
# Solution
Approach 1: recursion.
Approach 2: stack based -- visit the middle node, then push the right then left substree in stack.
Approach 3: stack based -- visit the middle node, then navigate down the left subtree, while keeping the right subtree in stack.
Approach 4: Morris traversal: stackless (saves space). It keeps track of the 'next' node (the top node to return to) by setting the right pointer of the rightmost leaf in the left subtree (and deleting these pointers later). Running time is tricky: the outer loop visits each node once -- O(N). The inner loop means each node needs to find it's prev (rightmost leaf on left subtree) twice. If you trace find prevs for all nodes in a tree, they add up to traversing every edge of a tree, and a tree of N nodes has N-1 edges. So the inner loops runs in O(N) cumulatively.
# Code (Python)
Approach 1:
def preorderTraversal(self, root):
# recursive
if not root:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
Approach 2:
def preorderTraversal(self, root):
# iterative, stack based
if not root:
return []
stack, result = [root], []
while stack:
node = stack.pop()
result.append(node.val)
# left subtree gets explored before right
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
Approach 3:
def preorderTraversal(self, root):
# iterative, stack based
if not root:
return []
stack, result = [root], []
while stack:
current = stack.pop()
# navigate down the left subtree while keeping the right subtree to be explored
while current:
result.append(current.val)
stack.append(current.right) # "push horizontal"
current = current.left
return result
Approach 4:
def preorderTraversal(self, root):
# Morris traversal
if not root:
return []
result = []
node = root
while node:
if not node.left: # happens either when a node doesn't have a left child, or a leaf node having a pseudolink
result.append(node.val)
node = node.right
else:
# for this node, search for the rightmost leaf on its left subtree (called 'prev', the last node to visit before it goes back to this node)
prev = node.left
while prev.right and prev.right != node:
prev = prev.right
if not prev.right:
# set the pseudolink
prev.right = node
result.append(node.val)
node = node.left
else: # prev.right == node --> we got to the back pointer
prev.right = None
node = node.right
return result
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// Recursion.
class Solution {
private:
vector<int> preorder;
void doPreorderTraversal(TreeNode* root) {
if (root == NULL)
return;
preorder.push_back(root->val);
doPreorderTraversal(root->left);
doPreorderTraversal(root->right);
}
public:
vector<int> preorderTraversal(TreeNode* root) {
doPreorderTraversal(root);
return preorder;
}
};
Approach 2:
// Iteration.
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> preorder;
stack<TreeNode*> st;
if (root)
st.push(root);
while (!st.empty())
{
TreeNode *curr = st.top();
st.pop();
preorder.push_back(curr->val);
if (curr->right)
st.push(curr->right);
if (curr->left)
st.push(curr->left);
}
return preorder;
}
};
Approach 3:
// Iteration.
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> preorder;
stack<TreeNode*> st;
TreeNode *curr = root;
while (curr)
{
preorder.push_back(curr->val);
if (curr->right)
st.push(curr->right);
curr = curr->left;
if (!curr && !st.empty())
{
curr = st.top();
st.pop();
}
}
return preorder;
}
};
Approach 4:
// Morris traversal.
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> preorder;
TreeNode *curr = root;
while (curr)
{
// Get the rightmost leaf of the left subtree.
TreeNode *leftRightmost = curr->left;
while (leftRightmost && leftRightmost->right)
leftRightmost = leftRightmost->right;
if (leftRightmost)
leftRightmost->right = curr->right;
if (curr->left)
curr->right = curr->left;
curr->left = NULL;
preorder.push_back(curr->val);
curr = curr->right;
}
return preorder;
}
};