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.

  • Bread First Search (BFS):

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.

postorder


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.

postorder

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.

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

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.

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.

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.

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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s