Tree traverse methods conclusion

Binary Tree Inorder, Preorder and Postorder traverse. The recursive way is pretty straight forward, now we gonna discuss the iterative ways.

First of all, we should be very familiar with the recursive way to traverse trees. Then we can convert it to iterative ways. For example, inorder traverse.

inorderTraverse(root)

   if(root->left) inorderTraverse(root->left)

   visit root

   if(root->right)  inorderTraverse(root->right)

For iterative way, we need a stack and a pointer to keep track of the parents and the current node we are visiting. 

1)create an empty stack S.

2)initialize current node as root.

3)push current node to S and set cur = cur->left until cur == NULL

4) if current is NULL and stack is not empty then 

  a) visit the top item in S

  b) pop out the top item from S

  c) set cur as the right child of cur

  d) go to 3)

5) if cur and S be both NULL, then it's done.

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> inorderTraversal(TreeNode *root) {
	vector<int> res;
	if(!root) return res;
	stack<TreeNode*> S;
	TreeNode *cur = root;
	//S.push(root);
	while(!S.empty()||cur != NULL){
	if(cur == NULL){
	cur = S.top();
	res.push_back(cur->val);
	S.pop();
	cur = cur->right;
	}
	else{
	S.push(cur);
	cur = cur->left;
	}
	}
	return res;
	}
	};

view raw binarytreeinordertraverse hosted with ❤ by GitHub

The iterative way of pre order traverse has almost the same idea.

While the post order iterative traverse is a little bit harder.

	/**
	* Definition for binary tree
	* 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;
	if(!root) return res;
	stack<TreeNode*> S;
	TreeNode *cur = root;
	while(!S.empty()||cur!=NULL){
	if(cur){
	res.push_back(cur->val);
	S.push(cur);
	cur = cur->left;
	}
	else{
	cur = S.top();
	S.pop();
	cur = cur->right;
	}
	}
	return res;
	}
	};

view raw BinaryTreePreOrderTraverse hosted with ❤ by GitHub