Preorder, Inorder, and Postorder Iteratively Summarization


  • 207

    Here I summarize the iterative implementation for preorder, inorder, and postorder traverse.


    Pre Order Traverse


    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);
                result.add(p.val);  // Add before going to children
                p = p.left;
            } else {
                TreeNode node = stack.pop();
                p = node.right;   
            }
        }
        return result;
    }
    

    In Order Traverse


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode node = stack.pop();
                result.add(node.val);  // Add after all left children
                p = node.right;   
            }
        }
        return result;
    }
    

    Post Order Traverse


    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);
                result.addFirst(p.val);  // Reverse the process of preorder
                p = p.right;             // Reverse the process of preorder
            } else {
                TreeNode node = stack.pop();
                p = node.left;           // Reverse the process of preorder
            }
        }
        return result;
    }

  • 22
    N

    Again, as I commented at in the most popular answer, strictly speaking, this solution for the post order is incorrect. Even though the final result is correct, imagine if there are topological dependencies among the nodes, the visiting order would be significant. Simply reversing the preorder result isn't right.


  • 0
    S

    Sorry if I missed your point, but how can a binary tree has topological dependencies?


  • 2
    G

    Nick's right. You're simply cheating. Because strictly speaking, you've already visited root before left and right.


  • 15
    O

    Your answer is short. The reverse of pre-order is skillful though may not be general. Here I attach my solution of postorderTrav without reversing pre-order. The key point is when you pop a node from stack, you ensure you have already explored its children.

    public class Solution {
        // Important, when you pop a node, ensure its children are traversed.
        public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> s = new Stack();
            List<Integer> ans = new ArrayList<Integer>();
            TreeNode cur = root;
            
            while (cur != null || !s.empty()) {
                while (!isLeaf(cur)) {
                    s.push(cur);
                    cur = cur.left;
                }
                
                if (cur != null) ans.add(cur.val);
                
                while (!s.empty() && cur == s.peek().right) {
                    cur = s.pop();
                    ans.add(cur.val);
                }
                
                if (s.empty()) cur = null; else cur = s.peek().right;
            }
            
            return ans;
        }
        
        private boolean isLeaf(TreeNode r) {
            if (r == null) return true;
            return r.left == null && r.right == null;
        }
    }

  • 1
    O

    Shorter one:

    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList();
            TreeNode p = root;
            Stack<TreeNode> st = new Stack();
            while (p != null || !st.empty()) {
                for (;p != null && !isLeaf(p); st.push(p), p = p.left);
                if (p != null) ans.add(p.val);
                for (;!st.empty() && st.peek().right == p; p = st.pop(), ans.add(p.val));
                p = st.empty() ? null : st.peek().right; 
            }
            return ans;
        }

  • 5
    O

    An alternative one:

    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList();
            if (root == null) return ans;
            Stack<TreeNode> st = new Stack();
            st.push(root);
            
            for (TreeNode p = root, prev; !st.empty();) {
                prev = p;
                p = st.peek();
                if (p.left != null && p.left != prev && p.right != prev) 
                    st.push(p.left);
                else
                if (p.right != null && p.right != prev) 
                    st.push(p.right);
                else
                    ans.add(st.pop().val);
            }
            return ans;
        }

  • 2
    Z

    I wouldn't say it's necessarily cheating but more of the nature of the data structure in use (tree), and so no matter what algorithm you use, you will have to visit the root before you can get to its children. It's actually the same for topological sort as well - you will have to follow the path first to find the nodes that are not depended by any other node first


  • 1
    F
    public List<Integer> postorderTraversal(TreeNode root) {
    	LinkedList<Integer> res = new LinkedList<Integer>();
    	if(root == null){
    		return res;
    	}
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	while(!stack.isEmpty() || root != null){
    		while(root != null){
    			stack.push(root);
    			res.addFirst(root.val);;
    			root = root.right;
    		}
    		root = stack.pop();
    		root = root.left;
    	}
    	return res;
    }

  • 0
    X

    is there any reason to use deque here??


  • 0
    W

    @xinying3 Stack is an obsolete class inherited from Vector (so wired), but Deque is a flexible interface which is obviously better than Stack. If you need to deal with concurrency, BlockingDeque is also a better one.


  • 1

    that's not cheating but this postorder traversal is useless in lots of cases.


  • 4
    R

    Here is my solution:

    public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            TreeNode pre = null;
            TreeNode current = root;
            while(current != null || !stack.isEmpty()) {
                while(current != null) {
                    stack.push(current);
                    current = current.left;
                }
                 current = stack.pop();
                if(current.right != null && pre != current.right) {
                    stack.push(current);
                    current = current.right;
                    continue;
                } 
                list.add(current.val);
                pre = current;
                current = null;
              
            }
            return list;
        }
    }
    

  • 1

    @root_010 Upvoted, just instead of pop and push back the current node, you could just use current = stack.peek(); to avoid unnecessary operations.
    Just last part of your code

    cur = stack.peek();
    if(cur.right != null && prev != cur.right)
    {
        cur = cur.right;
    }
    else
    {
        stack.pop();
        res.add(cur.val);
        prev = cur;
        cur = null;
    }
    

  • 1

    Strictly speaking, this algorithm is only for tree sequentialisation in the post order because you are not visiting the nodes in the post-order. Let's put it another way, if you are asked to do some task by traversing the tree in the post order (say, free a tree), you cannot use this algorithm.


  • 0

    @BetaGo checkout my solution. https://discuss.leetcode.com/topic/34258/iterative-method-to-do-three-kinds-of-traversal-just-like-recursive-method-only-changing-one-line-code.

    My iterative solution is as simple as recursive one and it's practical.


  • 0
    This post is deleted!

  • 0

    @jedihy It's a smart generalized way, using graph-alike traversal. But if you investigate the in-order search, you have more push/pop operations than others' solutions. And another drawback is, you need these additional visited flags.


  • 0

    @BetaGo More space might be consumed but it does not mean slower than other iterative solutions. Actually, I don't think my solution is something related to graph. It's emulating the stack in recursion or you can say emulating the real visiting order when doing traversal. It's very practical because I solved a lot of tree traversal problems using this method.

    EDIT: I think it's a kind of BFS but I 0,1 in tuple is not used for visit flag. They are used as command identifier to identify commands in recursion.


  • 0

    I didn't say you solution is slower. I was talking about the space complexity. Actually, if one solution consumes more space, we expect it should be faster. Kind of time-space tradeoff stuff. But for your solution, I don't see this time complexity advantage. Worse, have you investigated the in-order traversal? Some nodes are pushed/popped more than once. It has more stack operations compared with other solutions, which means it's slower.

    I don't know what your command identifier is meant for. But without doubt, I can regard it as visited flag to write the exactly same solution as yours.


Log in to reply
 

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