Three ways of Iterative PostOrder Traversing. Easy Explanation!


  • 2

    Three types of Iterative Postorder Traversals.

    1. Using 1 Stack. O(n) Time & O(n) Space
      This is similar to Inorder using 1 Stack. The difference is we keep track of the previously printed node in pre. And we only print a node if its right child is null or equal to pre.
      • Push all left nodes into the stack till it hits NULL.
      • root = s.peek()
      • if root.right = null or pre (Means we have traversed the right subtree already)
        • We print root and pop it from s.
        • Make pre = root
        • root = null (So we dont go down to left child again)
      • else
        • root = root.right (Traverse the right subtree before printing root)
      • Keep iterating till both the below conditions are met -
        • Stack is empty and
        • Root is NULL.
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> out = new ArrayList<Integer>();
    	if(root==null)
    		return out;
    	TreeNode pre=null;
    	Stack<TreeNode> s = new Stack();      
    	while(root!=null || !s.empty()){
    		if(root!=null){				
    			s.push(root);
    			root = root.left;
    		}
    		else{
    			root = s.peek();
    			if(root.right==null || root.right==pre){
    			    out.add(root.val);
    			    s.pop();
    			    pre=root;
    			    root = null;
    			}
    			else
    			    root = root.right;
    		}
    	}
    	return out;
    }
    
    1. Using 2 Stacks. O(n) Time & O(n) Space
      We use two stacks. Stack s is used to find and traverse the child nodes, and path stack keeps track of the path from the root to the current node. (This is usefull in certain problems like Binary Tree Paths and Path Sum ).
      • Initially we push the root into s.
      • Keep iterating with below logic till s is empty.
        • root = s.peek()
        • If the top elements of both the stacks are not the same :
          • Print root and push it into path.
          • Push root's children into s in reverse order. (Remember it's a stack!)
        • When top elements of both stacks are equal. (Which means we hit a deadend, and need to turn back)
          • Pop from both stacks.
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<Integer>();
        if(root == null)
            return out; 
        Stack<TreeNode> s = new Stack(), path = new Stack();
        s.push(root);
        while(!s.empty()){
            root = s.peek();
            if(!path.empty() && path.peek()==root){
                out.add(root.val);
    	    s.pop();
                path.pop();
            }
            else{                
                path.push(root);
                if(root.right != null)
                    s.push(root.right);
                if(root.left != null)
                    s.push(root.left);
            }
        }
        return out;
    }
    
    1. Using No Stacks (Morris Traversal). O(n) Time & O(1) Space
      Instead of using stacks to remember our way back up the tree, we are going to modify the tree to create upwards links. The idea is based on Threaded Binary Tree.
      Similar to Inorder Morris Traversal.
      0_1477341646335_postorder.jpg
      We reverse each diagonal shown in the picture (d1-d4), print it and re-reverse it.

      • Create a dummy node and make dummy.left = root.
      • root = dummy
      • Iterate till root is null.
        • If root has a left child.
          • Find the inorder predecessor => pre. (Inorder predecessor of root is the right most child of its left child)
            • pre.right = root (Make it point to root).
            • root = root.left.
          • If its already pointing to root (which means we have traversed it already and are on our way up.)
            • Reverse from root.left to pre.
            • Traverse from pre to root.left and print the nodes.
            • Re-reverse it back to normal.
            • pre.right = null.
            • root = root.right.
        • If left child is null
          • root = root.right. (We are climbing up our link.)
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<Integer>();
        if(root == null)
            return out;
        TreeNode dummy = new TreeNode(-1), pre = null;
        dummy.left = root; root = dummy;
        while(root != null){
            if(root.left != null){
                pre = root.left;
                while(pre.right != null && pre.right != root)
                    pre=pre.right;
                if(pre.right == null){
                    pre.right = root;
                    root = root.left;
                }
                else{
                    TreeNode node = pre;
                    reverse(root.left,pre);
                    while(node != root.left){
                        out.add(node.val);
                        node = node.right;
                    }
                    out.add(node.val);          // Print again since we are stopping at node=root.left
                    reverse(pre,root.left);
                    pre.right = null;
                    root = root.right;
                }
            }
            else{
                root = root.right;
            }
        }
        return out;
    }
    
    public void reverse(TreeNode from, TreeNode to){
        if(from == to)
            return;
        TreeNode prev = from, node = from.right;
        while(prev != to){
            TreeNode next = node.right;
            node.right = prev;
            prev = node;
            node = next;
        }
    }
    

    Also checkout Inorder & PreOrder :))


Log in to reply
 

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