Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
    }
}
share|improve this question

1 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.

share|improve this answer
    
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. –  Vogel612 Mar 31 '14 at 10:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.