[233333] Summary of the iterative traversal of Pre-order / In-order / Post-order


  • 3
    2

    Update : you can GET the" RUN on OJ directly C++ implementation " in the below first answer .

    First for the pre-order, it is easy to implement the stack-based iterative solution

    Pre-Order-Non-recursion-Traversal ....

     1) Create an empty stack nodeStack and push root node to stack.
     2) Do following while nodeStack is not empty.
         ….a) Pop an item from stack and print it.
         ….b) Push right child of popped item to stack
         ….c) Push left child of popped item to stack
    

    Here is the C++ implementation :

    // An iterative process to print preorder traversal of Binary tree
    void iterativePreorder(node *root)
    {
        // Base Case
        if (root == NULL)
           return;
     
        // Create an empty stack and push root to it
        stack<node *> nodeStack;
        nodeStack.push(root);
     
        /* Pop all items one by one. Do following for every popped item
           a) print it
           b) push its right child
           c) push its left child
        Note that right child is pushed first so that left is processed first */
        while (nodeStack.empty() == false)
        {
            // Pop the top item from stack and print it
            struct node *node = nodeStack.top();
            printf ("%d ", node->data);
            nodeStack.pop();
     
            // Push right and left children of the popped node to stack
            if (node->right)
                nodeStack.push(node->right);
            if (node->left)
                nodeStack.push(node->left);
        }
    }
    

    Inorder Tree Traversal without Recursion

       1) Create an empty stack S.
       2) Initialize current node as root
       3) Push the current node to S and set current = current->left until current is NULL
       4) If current is NULL and stack is not empty then 
              a) Pop the top item from stack.
              b) Print the popped item, set current = popped_item->right 
              c) Go to step 3.
       5) If current is NULL and stack is empty then we are done.
    

    Here is the C++ implementation ....

    int In_Order_Traversal(TreeNode* root) {
        stack<TreeNode*> st;
        
        while(root) {
            st.push(root);
            root = root->left;
        }
        
        while(!st.empty()) {
            TreeNode * n = st.top();
            st.pop();
            cout<<n->val<<endl;;
            TreeNode* right = n->right;
            while(right) {
                st.push(right);
                right = right->left;
            }
        }
        return 0;
    }
    

    How about the Post-Order ?

    Post-Order-Non-Recursive-Traversal

    Solution 1 : using 2 stacks

      int Post_Order_Traversal(TreeNode* root) {
            stack<TreeNode*> st1;
            stack<TreeNode*> st2;
            
            st1.push(root);
            while(!st1.empty()) {
                TreeNode* cur = st1.top();
                st2.push(cur);
                st1.pop();
                if(cur->left) st1.push(cur->left);
                if(cur->right) st1.push(cur->right);
            }
            while(!st2.empty()) {
                cout<<(st2.top())->val;
                st2.pop();
            }
            return 0;
        }
    

    Solution 2 ,

    You can also use one stack to do the post-order-traversal ....

    Here I do not talk about it .... YOU CAN refer to the below posts :

    http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/


  • 0
    2
    class Solution {
    public:
        int Test(TreeNode* root, int k) {
            stack<TreeNode*> st;
            Pre(root);
            cout<<endl;
            
            In(root);
            cout<<endl;
            
            Post(root);
            cout<<endl;
         
            return -1;
        }
        
        void Pre(TreeNode* root) {
            stack<TreeNode*> st;
            st.push(root);
            while(!st.empty()) {
                TreeNode* cur = st.top();
                st.pop();
                cout << cur->val << "-";
                if(cur->right)  st.push(cur->right);
                if(cur->left) st.push(cur->left);
            }
            return;
        }
        
        void In(TreeNode* root) {
            stack<TreeNode*> st;
            TreeNode* cur = root;
            while(cur) {
                st.push(cur);
                cur = cur->left;
            }
            while(!st.empty()) {
                TreeNode* cur = st.top();
                st.pop();
                cout << cur->val << "-";
                TreeNode* cur_right = cur->right;
                while(cur_right) {
                    st.push(cur_right);
                    cur_right = cur_right->left;
                }
            }
            return;
        }
        
        void Post(TreeNode* root) {
            stack<TreeNode*> st1, st2;
            st1.push(root);
            while(!st1.empty()) {
                TreeNode* cur = st1.top();
                st1.pop();
                st2.push(cur);
                if(cur->left) st1.push(cur->left);
                if(cur->right)  st1.push(cur->right);
            }
            while(!st2.empty()) {
                cout<<(st2.top())->val<<"-";
                st2.pop();
            }
            return;
        }
    };
    

    The above code can RUN, you can run it directly .

    For example ,

    For the test case :

        [1,2,3,4,5,6,7]
    

    It will output

      1-2-4-5-3-6-7-
      4-2-5-1-6-3-7-
      4-5-2-6-7-3-1-

  • 0
    F

    More clean iterative implementation

    
    
    //post order iterative traversal
    vector<int> postorderTraversal(TreeNode* root) {
    	vector<int> ans;
    	if (!root) return ans;
    	stack<TreeNode*> nodes;
    	TreeNode* pre = nullptr;
    	nodes.push(root);
    	while (!nodes.empty()) {
    		root = nodes.top();
    		if ((root->left == nullptr) && (root->right == nullptr) ||
    				(pre != nullptr && (root->left = pre || root->right == pre))) {
    			ans.push_back(root->val);
    			nodes.pop();
    			pre = root;
    		}
    		else {
    			if (root->right) nodes.push(root->right);
    			if (root->left) nodes.push(root->left);
    		}
    	}
    }
    
    
    //in order iterative traversal
    vector<int> inorderTraversal(TreeNode* root) {
    	vector<int> ans;
    	stack<TreeNode*> nodes;
    	while (root || !nodes.empty()) {
    		while (root) {
    			nodes.push(root);
    			root = root->left;
    		}
    		if (!nodes.empty()) {
    			root = nodes.top();
    			nodes.pop();
    			ans.push_back(root->val);
    			root = root->right;
    		}
    	}
    }
    
    //post order iterative traversal
    vector<int> postorderTraversal(TreeNode* root) {
    	vector<int> ans;
    	if (!root) return ans;
    	stack<TreeNode*> nodes;
    	nodes.push(root);
    	while (!nodes.empty()) {
    		root = nodes.top();
    		nodes.pop();
    		ans.push_back(root->val);
    		if (root->right) nodes.push(root->right);
    		if (root->left) nodes.push(root->left);
    	}
    	return ans;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.