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

	/**
	* 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<int> preorderTraversal(TreeNode* root) {
	vector<int> res;
	rec(res, root);
	return res;
	}
	void rec(vector<int> &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);
	}
	};

view raw

BT_Preorder_Rec.cpp

hosted with ❤ by GitHub

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.

	/**
	* 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<int> preorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode*> 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;
	}
	};

view raw

BT_Preorder_It.cpp

hosted with ❤ by GitHub

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

	class Solution {
	public:
	vector<int> preorderTraversal(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);
	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;
	}
	};

view raw

BT_Preorder_It02.cpp

hosted with ❤ by GitHub

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.

	/**
	* 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<int> preorderTraversal(TreeNode* root) {
	vector<int> 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;
	}
	};

view raw

BT_Preorder_Morris.cpp

hosted with ❤ by GitHub

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.

	/**
	* 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<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	rec(res, root);
	return res;

	}
	void rec(vector<int> &res, TreeNode* root){
	if(root == NULL) return;

	rec(res, root->left);
	rec(res, root->right);
	res.push_back(root->val);
	}
	};

view raw

BT_Postorder_Rec.cpp

hosted with ❤ by GitHub

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.

	/**
	* 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<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode*> 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;
	}
	};

view raw

BT_Postorder_It.cpp

hosted with ❤ by GitHub

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…

共享此文章：

Like this:

Related

Leave a Reply Cancel reply