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:

	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:

	class Solution {
	private:
	void dfs(vector<int>& res, TreeNode* root){
	if(root == nullptr) return;
	dfs(res, root->left);
	res.push_back(root->val);
	dfs(res, root->right);
	}
	public:
	vector<int> inorderTraversal(TreeNode* root) {
	vector<int> res;
	dfs(res, root);
	return res;
	}
	};

view raw

BT_Inorder_Rec.cpp

hosted with ❤ by GitHub

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.

	class Solution {
	public:
	vector<int> inorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode*> 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;
	}
	};

view raw

BT_Inorder_It01.cpp

hosted with ❤ by GitHub

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.

	class Solution {
	public:
	vector<int> inorderTraversal(TreeNode* root) {
	vector<int> res;
	if(!root) return res;
	stack<TreeNode*> 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;
	}
	};

view raw

BT_Inorder_It02.cpp

hosted with ❤ by GitHub

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

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:

	class Solution {
	private:
	void dfs(vector<vector<int>>& 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<int>());
	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<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> res;
	if(!root) return res;
	dfs(res, root, 0);
	return res;
	}
	};

view raw

BT_LevelOrder_Rec.cpp

hosted with ❤ by GitHub

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.

	class Solution {
	public:
	vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> res;
	if(!root) return res;
	//We can use the length of the tree to indicate the elements in this level
	//A common trick, remember
	queue<TreeNode*> Q;
	Q.push(root);
	while(!Q.empty()){
	int len = Q.size();
	vector<int> tempStack;
	for(int i = 0; i < len; i++){
	TreeNode* cur = Q.front();
	Q.pop();
	tempStack.push_back(cur->val);
	if(cur->left) Q.push(cur->left);
	if(cur->right) Q.push(cur->right);
	}
	res.push_back(tempStack);
	}
	return res;
	}
	};

view raw

BT_LevelOrder_It.cpp

hosted with ❤ by GitHub

Time Complexity: O(n)

Space Complexity: O(h)

Thank you for reading.

In-order Traversal

Solution 1: Recursion

Solution 2: Iteration

Level-order Traversal (BFS)

Solution 1: Recursion

Solution 2:

共享此文章：

Like this:

Related

Leave a Reply Cancel reply