CODEWITHSUNDEEP
algorithmdata-structures
Mingtao Zhang
Mingtao Zhang

Reputation: 148

Tree Postorder Traversal performance

I tried to work on my own to get iterative postorder traversal. My solution got Time Limited Exceeded in Leetcode Online Judge

public List<Integer> postorderTraversalIterativel(TreeNode root) {
    List<Integer> ret = new LinkedList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode parent = stack.peek(), child = null;
            if (parent.right == null) {
                // pop hard
                stack.pop();
                while (parent.right == child && !stack.isEmpty()) {
                    child = parent;
                    ret.add(child.val);
                    parent = stack.pop();
                }
            } else {
                cur = parent.right;
            }
        }
    }
    return ret;
}

while the official implementation from wikipedia could pass the test.

public List<Integer> postorderTraversalIterativel(TreeNode root) {
    List<Integer> ret = new LinkedList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root, lastVisited = null;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode parent = stack.peek();
            if (parent.right != null && lastVisited != parent.right) {
                // make sure pop all the node has right child of the
                // previous pop
                cur = parent.right;
            } else {
                stack.pop();
                ret.add(parent.val);
                lastVisited = parent;
            }
        }
    }
    return ret;
}

by inspecting the code, I am unable to see why my implementation is slower than the official one. Could anyone point out what's happening? (It's possible that my solution is logically wrong, but the one failed my solution in timing I have unit tested, and the unit test finishes quick ...). Any comments are welcome.

public void testPostorderTraversal1() {
    TreeNode root = new TreeNode(3);
    TreeNode right = new TreeNode(1);
    TreeNode rightLeft = new TreeNode(2);
    root.right = right;
    right.left = rightLeft;

    List<Integer> list = new LinkedList<Integer>();
    list.add(2);
    list.add(1);
    list.add(3);

    assertEquals(list.toString(), sut.postorderTraversal(root).toString());
}

public void testPostorderTraversal2() {
    TreeNode root = new TreeNode(1);
    TreeNode right = new TreeNode(2);
    root.right = right;

    List<Integer> list = new LinkedList<Integer>();
    list.add(2);
    list.add(1);

    assertEquals(list.toString(), sut.postorderTraversal(root).toString());
}

Upvotes: 0

Views: 227

Answers (1)

Mastojun
Mastojun

Reputation: 202

Your code has possible to do Infinite loop.

Your 'testPostorderTraversal1' unitest is not finish.

If there is any node that has right child node that has left child node, can't finish.

Upvotes: 1

Related Questions