Tree Traversal (In-order / Level-order)

Last time we have talked about the pre-order traversal and post-order traversal of a binary tree (see here). Now let’s look at another two traversals and how we can implement the traversal algorithm in C++.

postorder

Let’s first define the tree node here. For each node, we will have a value and two tree node pointers which represent the left subtree and right subtree:


In-order Traversal

Let’s first look at the in-order traversal. Basically, we will always traverse from the left branch first, then the root, and finally the right branch. Look at the above picture, the number indicates the order the node will be visited.

One of the important features of in-order traversal is that if we are given a binary search tree, the in-order traversal will give us the sequence of nodes in ascending order. An example of how this works is demonstrated below:

In-order Traversal Example:

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

Output: [1,3,2]

Solution 1: Recursion

Recursive implementation is trivial. We provide the code here:

Time Complexity: O(n)

Space Complexity: O(h)


Solution 2: Iteration

The iterative version of in order traversal is not hard as well. The general pattern will be we first search the left branch of the tree and push all the left nodes to the stack. When we reach the nullptr, we pop the last element and put it in our result. Then we examine the right tree using the same pattern here.

A slightly different version here. Note we can easily convert the following implementation to pre-order traversal as well as the depth-first search of a binary tree. We use the pre pointer to keep track of the right node we have already visited.

Time Complexity: O(n)

Space Complexity: O(h)


Level-order Traversal (BFS)

The level order traversal of the binary tree is actually the breadth first search. We iterate through each tree node from top to bottom and left to right. During the traversal, we save the elements from each level to an array and finally print out the levels. An example of how this work is illustrated below:

Level-order Traversal Example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution 1: Recursion

The recursive version is actually interesting. We need to maintain a variable called level in order to check whether we are at a new level. Then we do the normal depth-first search, whenever we find a new element, we will put it to the corresponding level. Here is the implementation:

Time Complexity: O(n)

Space Complexity: O(h)


Solution 2:

Just like the typical BFS algorithm, we will utilize the queue data structure in the iterative implementation. We could use the size of the queue to indicate the number of the previous level.

Time Complexity: O(n)

Space Complexity: O(h)


Thank you 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