# 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++.

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:

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.

 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

view raw

BT_TreeNode.cpp

hosted with ❤ by GitHub

## 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:

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 { private: void dfs(vector& res, TreeNode* root){ if(root == nullptr) return; dfs(res, root->left); res.push_back(root->val); dfs(res, root->right); } public: vector inorderTraversal(TreeNode* root) { vector res; dfs(res, root); return res; } };

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.

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 inorderTraversal(TreeNode* root) { vector res; stack st; if(root == nullptr) return res; //Maintain a variable for current value. For inorder traversal, //we need to push left nodes to our stack, then add the value to res. TreeNode* cur = root; while(cur || !st.empty()){ if(cur!= nullptr){ st.push(cur); cur = cur->left; } else{ //We need to update cur. because currentlt it's nullptr cur = st.top(); res.push_back(cur->val); st.pop(); cur = cur->right; } } return res; } };

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.

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 inorderTraversal(TreeNode* root) { vector res; if(!root) return res; stack st; TreeNode* pre = nullptr, *cur = root; while(cur || !st.empty()){ while(cur){ st.push(cur); cur = cur->left; } cur = st.top(); // pop immediately to avoid repetitively visit st.pop(); res.push_back(cur->val); 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; } pre = cur; cur = nullptr; } return res; } };

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:

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 { private: void dfs(vector>& res, TreeNode* node, int level){ int len = res.size(); //How to maintain the current layer list is critical here. if(res.empty() || len < level + 1) res.push_back(vector()); res[level].push_back(node->val); if(node->left) dfs(res, node->left, level+1); if(node->right) dfs(res, node->right, level + 1); } public: vector> levelOrder(TreeNode* root) { vector> res; if(!root) return res; dfs(res, root, 0); return res; } };

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.

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.