CODEWITHSUNDEEP
javatreebinary-search-treetraversaltree-traversal
buddybuddybuddybuddy
buddybuddybuddybuddy

Reputation: 41

InOrder traversal of BST...why is loop condition "cur != null || !stack.empty()" ?"

This is the InOrder traversal (left, root, right) for a BST:

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}

I cannot wrap my head around why the 'while' loop condition is cur != null || !stack.empty().

I particularly am MOST confused by "cur != null". Why is this even necessary?

From logic of an 'or' statement, A || B means A and B have to be both false in order for the loop to break.

So the loop will break once cur == null and the stack is empty.

Why do we even need to care if cur == null? Isn't this extraneous and not necessary?

Note: Original LC problem (for testing) -- https://leetcode.com/problems/binary-tree-inorder-traversal/

Upvotes: 0

Views: 282

Answers (2)

Sweeper
Sweeper

Reputation: 270860

If you only continue the loop if the stack is not empty, the loop will not start at all because the stack is empty.

Even if you use a do...while loop, the condition of "stack is not empty" is not enough.

Consider a tree without left nodes:

root
   \
    \
    node1
      \
       \
      node2

The algorithm would add root to the stack, then pop it, then add it to the list. After that, curr will be the right node of root, which is node1. At this point, the stack is empty, but curr is not null.

The loop would stop at this point, which is clearly not correct.

The while loop should only stop when both the stack is empty and there is no right node (i.e. continue if stack is empty or there is a right node).

Upvotes: 0

the Hutt
the Hutt

Reputation: 18398

Without cur!=null check, if you call inorderTraversal(null); it'll throw EmptyStackException.

If you are running this in any IDE like Eclipse, you can use debug feature. Or manually try execute simple input [1,null,2]. After first iteration the stack will be empty but curr will not be null.

Upvotes: 0

Related Questions