[Re-view] Tree Traversal (PreOrder, InOrder, PostOrder): Recursion and Non-Recursion(Iteration)
Introduction
In this post, I would like to talk one important algorithm---- Tree Traversal. Tree traversal is a basic but crucial concept in data structure and algorithm, which is also very hot in interviews. In this post, I assume that you have already had the idea of "what is binary tree?", "what is tree traversal?", and "what is stack?". I will focus on
Recursive and
Non-Recursive traversal, for
PreOrder, InOrder, PostOrder, and Level Order of binary tree. Algorithm description with GIF animation are provided along with the C++ implementations. The code can be run and tested in leetcode online judge as well.
Actually the "three order" traversal is easily to memorize in this way:
Where is the root? When the root is in the first place to be visited (root->left->right), then it is "pre" order, when the root is in the middle to be visited (left->root->right), then it is "in" order, and when the root is last to be visited, it is "post" order.
PreOrder Traversal:
Description:
PreOrder traversal is according to the root, left and right order traversing the binary tree.
Recursive traversal is straightforward: we first visit the root node, then traverse its left child, then its right child.
Non-Recursive traversal is to ulitize the data structure stack. There are three steps for this algorithm:
(1) Initialize the stack. Push the root node into stack.
(2) While the stack is not empty do:
(a) Pop the top node from the stack.
(b) Store the top node
(c) Push the top node's right child into stack
(d) Push the top node's left child into stack
(3) Output the stored sequence.
Animation(non-recursive):
Code (PreOrder Traversal):
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// preorder traversal: recursion
void pre_recur(TreeNode* root, vector<int> &res){
if (!root){ //if null node, return
return;
}else{
res.push_back(root->val); // traverse root child
if (root->left){
pre_recur(root->left,res); //traverse left child
}
if (root->right){
pre_recur(root->right,res); //traverse right child
}
}
}
// preorder traversal: non-recursion
void pre_norecur(TreeNode* root,vector<int> &res){
stack<TreeNode*> st;
st.push(root); //initialize stack
TreeNode* tmp;
while (!st.empty()){
tmp=st.top(); //get the top node in stack
st.pop();
res.push_back(tmp->val); //store the root value
if (tmp->right){st.push(tmp->right);} //push right child into stack
if (tmp->left){st.push(tmp->left);} //push left child into stack
}
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root){return res;}
//pre_recur(root,res); //recursive traversal
pre_norecur(root,res); //non-recursive traversal
return res;
}
};
InOrder Traversal:
Description:
InOrder traversal is according to the left, root, and right order traversing the binary tree.
Recursive traversal is straightforward: we first traverse the left child, then visit the root node, then traverse the right child.
Non-Recursive traversal is to ulitize the data structure stack. There are three steps for this algorithm:
(1) Initialize the stack. Set root as the current node. Push the current node into stack.
(2) Loop until finished (while true):
(a) If current has left child:
(i)Push left child into stack.
(ii)Current node = current node's left child
(b) If current has NO left child:
(i)If stack is empty: exit
(ii)If stack is NOT empty:
Pop the top node in the stack.
Store the top node for output.
Set current node = top node's right child.
(3) Output the stored sequence.
Animation(non-recursive):
Code (InOrder Traversal):
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// inorder traversal: recursion
void in_recur(TreeNode* root, vector<int> &res){
if (!root){ //if null node, return
return;
}else{
if (root->left){in_recur(root->left,res);} //traverse left child
res.push_back(root->val); // traverse root child
if (root->right){in_recur(root->right,res);} //traverse right child
}
}
// inorder traversal: non-recursion
void in_norecur(TreeNode* root,vector<int> &res){
stack<TreeNode*> st;
while (true){
if (root){ // keep pushing the left child of current node
st.push(root);
root=root->left;
}else{
if (!st.empty()){
TreeNode* top = st.top(); //pop the top node in the stack
st.pop();
res.push_back(top->val); //output the top node
root=top->right; //set current node=right child of top node
}else{
break; //if the stack is empty, then exit
}
}
}
}
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
if (!root){return res;}
//in_recur(root,res); //recursive traversal
in_norecur(root,res); //non-recursive traversal
return res;
}
};
PostOrder Traversal:
Description:
PostOrder traversal is according to the left, right, and root order traversing the binary tree.
Recursive traversal is straightforward: we first traverse the left child, then traverse the right child, then visit the root node.
Non-Recursive traversal is to ulitize the data structure stack. Two stacks is used in this algorithm. Stack 2 is used to store the result. There are three steps:
(1) Initialize the stack. Push the root node into stack.
(2) While the stack is not empty do:
(a) Pop the top node from the stack 1.
(b) Push the top node into stack 2.
(c) Push the top node's left child into stack 1.
(d) Push the top node's right child into stack 1.
(3) Pop all the nodes in Stack 2 to get the result.
Animation(non-recursive):
Code (PostOrder Traversal):
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// postorder traversal: recursion
void post_recur(TreeNode* root, vector<int> &res){
if (!root){ //if null node, return
return;
}else{
if (root->left){
post_recur(root->left,res); //traverse left child
}
if (root->right){
post_recur(root->right,res); //traverse right child
}
res.push_back(root->val); // traverse root child
}
}
// postorder traversal: non-recursion
void post_norecur(TreeNode* root,vector<int> &res){
stack<TreeNode*> st1;
stack<TreeNode*> st2;
st1.push(root); //initialize stack one
TreeNode* tmp;
while (!st1.empty()){
tmp=st1.top(); //get the top node in stack 1
st1.pop();
st2.push(tmp); //push into stack 2
if (tmp->left){st1.push(tmp->left);} //push left child into stack 1
if (tmp->right){st1.push(tmp->right);} //push right child into stack 1
}
while (!st2.empty()){ //output the stack 2
tmp=st2.top();
st2.pop();
res.push_back(tmp->val);
}
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (!root){return res;}
//post_recur(root,res); //recursive traversal
post_norecur(root,res); //non-recursive traversal
return res;
}
};
