Binary Search Tree Inorder traversal cant understand solution

Question

Hi I am currently following leetcode interview questions and I have this solution that works but i cant understand 2 things

Solution Code

public class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

I have added an image to give reference to the values in the tree for solution [1]: https://i.sstatic.net/CqN9Q.png

What I don't understand is that the while loop until curr is not null or stack is empty however when we traverse down the left side we reach end then break inner loop, pop stack = curr, add to list and then equal curr to curr.right.

That is what I dont understand? In the image attached the left most node value is 4 which has no children which means its right child would equal to null then breaking the outer while loop ending the solution?

Second question the Time complexity is O(n) in the solution but would it not be O(n) squared because we have a loop in a loop?

Appreciate all help to point out what I am not fully understanding

thank you :)

Answer 1

A useful approach to understand this is through dry-running the code. For the example that you provided, the trace is as follows.

1. Initially curr = 1
2. We enter the outer while loop. And we won't exit from it unless both curr = null and the stack is empty.
3. Because of the inner while we reach the leftmost leaf node. curr = 4
4. The next iteration of the inner loop causes curr to be null so we break out from it. At this point 4 is popped from the stack and inserted in the list.
5. curr goes to the right child of 4, which is null.
6. In the next iteration of outer loop, curr is null. However, since the stack is still not empty we still enter the outer loop once again. We don't enter the inner loop however since curr is null.
7. We pop an element from the stack. This time it being 2. Remember stack is LIFO (Last in first out)

As for the overall time complexity. Two nested loops don't necessarily translate to a quadratic complexity. The overall complexity is still O(n) since each node in the tree is visited atmost once.