Binary tree level order traversal algoritm I am trying to solve this Binary tree lever order traversal:




Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7]
  [9,20],
  [3],
]



How can I improve the speed of the code below? It always gives me a time exceed error.



/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    public ArrayList&lt;ArrayList&lt;Integer&gt;&gt; levelOrderBottom(TreeNode root) {
        ArrayList&lt;ArrayList&lt;Integer&gt;&gt; tree = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt;();
        Stack&lt;Integer&gt; stack = new Stack&lt;Integer&gt;();
        ArrayList&lt;Integer&gt; node = new ArrayList&lt;Integer&gt;();

        this.iterateAll(root, stack);

        while (!stack.empty()) {
            if (stack.peek() != null) {
                node.add(stack.pop());
                if (!stack.isEmpty()) {
                    if (stack.peek() != null) {
                        tree.add(node);
                        node = new ArrayList&lt;Integer&gt;();
                    } else {
                        stack.pop();
                        if (!stack.isEmpty()) {
                            if (stack.peek() != null) {
                                tree.add(node);
                                node = new ArrayList&lt;Integer&gt;();
                            }
                        }
                    }
                } else {
                    tree.add(node);
                }
            } else {
                stack.pop();
            }
        }
        return tree;
    }

        public Stack&lt;Integer&gt; iterateAll(TreeNode root, Stack&lt;Integer&gt; stack) {
        if (root != null) {
            stack.push(root.val);
            if (root.right != null) {
                iterateAll(root.right, stack);
            } else {
                stack.push(null);
            }

            if (root.left != null) {
                iterateAll(root.left, stack);
            } else {
                stack.push(null);
            }
        }
        return stack;
    }
}
Depending on number of nodes in your tree, recursive post-order traversal of the tree, might let you run into problems on the stack. If the number of nodes is huge, you might need to consider a non-recursive post-order traversal.

Have a look at http://leetcode.com/2010/10/binary-tree-post-order-traversal.html, which describes multiple solutions, both iterative and non-recursive.

On think to keep in mind is that the non-recursive algorithms use more memory, as it need to push nodes to a stack.

You might also consider doing a post-order tree traversal enumerator, but that might be for another day.