# Tree Traversal (preorder / postorder)

Let’s continue…

First, I want to cite a great explanation about tree traversal. There are generally two approaches related to tree traversal: BFS and DFS.

We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

• Depth First Search (DFS):

In this strategy, we adopt the `depth` as the priority, so that one would start from a root and reach all the way down to a certain leaf, and then back to root to reach another branch.

The DFS strategy can further be distinguished as `preorder`, `inorder`, and `postorder` depending on the relative order among the root node, left node and right node.

On the following figure the nodes are numerated in the order you visit them, please follow `1-2-3-4-5` to compare different strategies. Problem Statement:

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]``

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution One – Recursion:

Although it might be trivial when solving this problem using recursion, however, let’s still take a look at recursion solution. If we take a close look at the picture, the preorder traversal will always visit root first, then the left child, then the right child. So in our recursive function, we need to follow this rule. We first note down the value, then go left, then go right. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector preorderTraversal(TreeNode* root) { vector res; rec(res, root); return res; } void rec(vector &res, TreeNode* root){ if(root == NULL) return; //We first record the root. res.push_back(root->val); rec(res, root->left); rec(res, root->right); } };

Time Complexity: O(n) we need to visit each node once.

Space Complexity: O(h) h is the height of a binary tree. At most O(n), at least O(lg n).

Solution Two – Iteration:

The problem requires us to traverse the tree iteratively. Typically, if we want to convert the depth first search to iterative version, we need to maintain a stack to store the future steps. When we traverse all the nodes in the tree, our stack will be empty and we will exit the loop (similar to call stack in DFS version). That’s how iteration works.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector preorderTraversal(TreeNode* root) { vector res; stack st; if(root == NULL) return res; st.push(root); while(!st.empty()){ TreeNode* temp = st.top(); st.pop(); res.push_back(temp->val); if(temp->right != NULL) st.push(temp->right); if(temp->left != NULL) st.push(temp->left); } return res; } };

A slightly different implementation. This implementation is easy to convert to in-order traversal. Basically, the cost should be the same:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: vector preorderTraversal(TreeNode* root) { vector res; if(!root) return res; stack st; TreeNode* pre = nullptr, *cur = root; while(cur || !st.empty()){ while(cur){ st.push(cur); res.push_back(cur->val); cur = cur->left; } cur = st.top(); if(cur->right && cur->right != pre){ cur = cur->right; //We need to continue for the next loop in order //to get the most left nodes to stack continue; } st.pop(); pre = cur; cur = nullptr; } return res; } };

Time Complexity: O(n)

Space Complexity: O(h)

Solution Three – Morris Traversal:

Morris Traversal is an interesting tree traversal algorithm which is presented by Joseph Morris. This algorithm utilizes the space in the tree and will provide the O(1) space complexity for tree traversal.

Here the idea is to go down from the node to its predecessor, and each predecessor will be visited twice. For this go one step left if possible and then always right till the end. When we visit a leaf (node’s predecessor) first time, it has a zero right child, so we update output and establish the pseudo link `predecessor.right = root` to mark the fact the predecessor is visited. When we visit the same predecessor the second time, it already points to the current node, thus we remove pseudo link and move right to the next node.

If the first one step left is impossible, update output and move right to next node.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector preorderTraversal(TreeNode* root) { vector res; TreeNode* node = root; while(node != NULL){ if(node->left == NULL){ res.push_back(node->val); node = node->right; } else{ TreeNode* predecessor = node->left; while(predecessor->right && predecessor->right != node){ predecessor = predecessor->right; } if(predecessor->right == NULL){ res.push_back(node->val); predecessor->right = node; node = node->left; } else{ node = node->right; predecessor->right = NULL; } } } return res; } };

Time Complexity: O(n)

Space Complexity: O(1)

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

`Input: `[1,null,2,3]` 1 \ 2 / 3 Output: `[3,2,1]``

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution One – Recursion:

The similar thing to preorder traversal.  The only thing we need change is the order of the sub tree traversal. This time we start from left, then right and finally root.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector postorderTraversal(TreeNode* root) { vector res; rec(res, root); return res; } void rec(vector &res, TreeNode* root){ if(root == NULL) return; rec(res, root->left); rec(res, root->right); res.push_back(root->val); } };

Time Complexity: O(n)

Space Complexity: O(h)

Solution Two – Iteration:

The similar thing to preorder traversal.  We still need to maintain a stack in the iterative version. This time, we also need to adjust the traversal order, we first start from root, then the right, and finally left. After our iteration, we have to reverse the result array in order to get the correct answer.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector postorderTraversal(TreeNode* root) { vector res; stack st; if(root == NULL) return res; st.push(root); while(!st.empty()){ TreeNode* temp = st.top(); st.pop(); res.push_back(temp->val); if(temp->left != NULL) st.push(temp->left); if(temp->right != NULL) st.push(temp->right); } reverse(res.begin(), res.end()); return res; } };

Time Complexity: O(n)

Space Complexity: O(1)

The discussion about the in-order and level-order traversal can be found here.

That’s all for today, thanks for reading…