GO Classes DPP | PYTHON & DSA |BST

Answer 1

X means there is no left node of $60$.

In an iterative in-order traversal using a stack, the maximum stack size corresponds to the maximum depth (or height) of the tree being explored. We push all ancestors of a node onto the stack as we travel down to the leftmost child.

• Path $\mathbf{1}: 45 \rightarrow 20 \rightarrow 10$ (Stack size $3: [45,20,10])$.
   
• Path $\mathbf{2}: 45 \rightarrow 80 \rightarrow 60 \rightarrow 70$ (Stack size $4: [45,80,60,70])$

When the traversal reaches the leaf node $\mathbf{7 0}$, the stack contains all its ancestors that are still being processed. This results in the maximum stack size.

Correct Option: D. $\mathbf{4}$

Comments

Don't we pop 45 before visiting the right subtree as it is in-order traversal, if that is the case then shouldn't it be 3?

---

OPERATION	STACK
INITIAL	[ ]
PUSH 45	[ 45 ]
PUSH 20	[ 45 , 20 ]
PUSH 10	[ 45, 20, 10 ]  (Max)
POP 10	[ 45, 20 ]
POP 20	[ 45 ]
PUSH 30	[ 45, 30 ]
POP 30	[ 45 ]
POP 45	[ ]
PUSH 80	[ 80 ]
PUSH 60	[ 80, 60 ]
POP 60	[ 80 ]
PUSH 70	[ 80, 70 ]
POP 70	[ 80 ]
POP 80	[ ]
PUSH 90	[ 90 ]
POP 90	[ ]