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

Question

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/

Answer 1

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