Binary tree level order traversal algoritm

Question

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<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
 ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>();
 Stack<Integer> stack = new Stack<Integer>();
 ArrayList<Integer> node = new ArrayList<Integer>();
 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<Integer>();
 } else {
 stack.pop();
 if (!stack.isEmpty()) {
 if (stack.peek() != null) {
 tree.add(node);
 node = new ArrayList<Integer>();
 }
 }
 }
 } else {
 tree.add(node);
 }
 } else {
 stack.pop();
 }
 }
 return tree;
 }
 public Stack<Integer> iterateAll(TreeNode root, Stack<Integer> 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;
 }
}

Answer 1

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.

• Vogel612: you might want to write a little sum up of your link, in case it goes down, I think some pseudocode or even just a short explanation of the algorithm would be enough.