[Leetcode/Stack,Tree] 897. Increasing Order Search Tree

 

✅ Iterative in-order traversal using a stack

class Solution:
    def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack = []
        dummy = TreeNode(-1)  # Dummy node to build the result tree
        curr = dummy          # Pointer to build the new tree
        node = root           # Start traversal from the root
        
        while stack or node:
            # 1. Go as left as possible
            while node:
                stack.append(node)
                node = node.left
            
            # 2. Visit the node at the top of the stack
            node = stack.pop()

            # 3. Rewire the tree: cut the left, connect to right of curr
            node.left = None
            curr.right = node
            curr = node

            # 4. Move to the right subtree
            node = node.right
        
        return dummy.right

🧩 Line-by-Line Breakdown:

stack = []

• We create an empty list to act as our stack.
• This stack will help us remember the path back up the tree (because we don’t have recursion here).

---

dummy = TreeNode(-1)

• We create a dummy node to anchor our new tree.
  • 이 문맥에서 dummy; '고정시키다'는 결과 트리의 루트 노드를 안정적으로 연결하기 위해 더미 노드를 사용한다는 의미로, 계산의 시작점을 제공하는 역할을 한다.
• It makes it easier to return the final result later (dummy.right will be the actual root of the new tree).

---

curr = dummy

• This is a pointer we’ll use to build the new tree.
• As we go through each node in in-order order, we’ll attach it to curr.right and then move curr forward.

---

node = root

• This is our traversal pointer — we’ll use node to walk through the original tree.

---

while stack or node:

• This is the main loop.
• We keep going while:
  • We still have nodes to visit (node is not None), or
  • We have nodes on the stack waiting to be processed (i.e., we’ve gone as left as we could and are now backtracking).

---

while node:

• This inner loop pushes all the left children onto the stack.
• We keep going left until we reach a node with no left child.

---

stack.append(node)

• Add the current node to the stack, so we can come back to it after finishing its left subtree.

---

node = node.left

• Move left, continuing the in-order traversal logic.

---

node = stack.pop()

• We’ve gone as far left as we can — now pop the last added node.
• This is the "in-order" step — visit the node after its left subtree.

---

node.left = None

• In the new tree, all .left pointers should be None (we’re flattening it into a right-only chain).

---

curr.right = node

• Attach the current node to the .right of the previously processed node (curr).

---

curr = node

• Move curr forward to keep building the new tree.

---

node = node.right

• Now shift to the right subtree of the current node — the next in-order step.

---

return dummy.right

• Done! The new root is the right child of the dummy node.

---

🧠 Visual Example:

Given:

    2
   / \
  1   3

 

Output (flattened):

1
 \
  2
   \
    3

Stack trace during traversal:

• Go left from 2 → push 2, go to 1
• Go left from 1 → push 1, node becomes None
• Pop 1 → add to result, move to 1’s right (None)
• Pop 2 → add to result, move to 2’s right (3)
• Go left from 3 → push 3, node becomes None
• Pop 3 → add to result

Done.