@allbugs said in A very concise recursive solution:

the time is O(n), but the rec

You are right. The time complexity is O(n). It is because every node is processed only once.

To calculate space complexity, let's try to simulate the stack manually for the tree 2->1->3(inoder sequece).

First, root (1) is processed. ie. it is pushed into the stack.
Then, root.left is processed. now stack has 1 and 2.
Then when we do root.left again, it is null and hence we start popping out.

So at any instance, stack will only contain log n entries. This is for a balanced tree.

But for worst case space complexity, we usually consider a skewed tree. So considering a left skewed tree, it will contain all n elements in the stack before u start popping out. Therefore, the worst case space complexity would be O(n). Let me know, if it is otherwise.