Exercises — BST — inorder gives sorted order

Inorder = Left, Node, Right applied recursively. Dive to the leftmost node first (smallest), then climb. $1,3,6,8,10,14$ Why: every node is emitted only after its entire smaller-left family. The list is sorted — as guaranteed for any BST.

False. Postorder is Left, Right, Node — the node comes last, so the root of Tree A (8) would be printed at the very end, not in its sorted slot. Only inorder (L, N, R) sorts a BST. See Tree Traversals for the others. Postorder of Tree A: $1,6,3,14,10,8$ — clearly not sorted.

Dive-left pushes, pop emits, then go right and dive-left again.

Output: $1,3,6,8,10,14$. Why the stack? It remembers the postponed "visit node + go right" work of each ancestor while we dived left.

Inorder emits in increasing order, so the $k$-th emitted value is the $k$-th smallest. Count emissions and stop at the 3rd: $1(\text{1st}),3(\text{2nd}),6(\text{3rd})\Rightarrow \text{answer }6.$ This is exactly the early-stop trick of Kth Smallest Element in BST — you never touch 8, 10, 14.

Insert one by one, each key going left if smaller, right if larger, from the root down:

• 5 → root
• 2 < 5 → left of 5
• 8 > 5 → right of 5
• 1 < 5, < 2 → left of 2
• 3 < 5, > 2 → right of 2

      5
     / \
    2   8
   / \
  1   3

Inorder = $1,2,3,5,8$ — sorted, as the invariant promises, regardless of insertion order.

No. Run inorder: dive left of 5 → 3; emit 3; back to 5, emit 5; go right to 7, dive left → 4; emit 4; emit 7. $3,5,4,7$ Here $5>4$ but 5 comes before 4 — the sequence is not increasing, so it is not a BST. The offender: node 4 sits in 5's right subtree yet is smaller than 5. This is the classic Validate BST pitfall.

Every node inherits an allowed open interval $(\text{low},\text{high})$ from its ancestors:

• Root 5: interval $(-\infty ,+\infty )$.
• Right child 7: must be $>5$, so interval $(5,+\infty )$.
• 7's left child 4: must be $>5$ (from the ancestor 5) and $<7$, so interval $(5,7)$.

But $4\notin (5,7)$. The local parent–child check only tested $4<7$ and forgot the inherited lower bound $5$ coming from the grandparent. Inorder catches this automatically because 4's position after 5 exposes the descent.

• Time: each of $n$ nodes is visited once → $O(n)$, always.
• Space: the recursion/stack depth equals the tree height $h$ → $O(h)$.
  • Balanced: $h=O(\log n)$.
  • Skewed (a straight line, e.g. inserting $1,2,3,4,5$): $h=n$, so space $O(n)$.

Why check $>$ not $\ge$? With distinct keys a valid BST is strictly increasing; using $\ge$ would wrongly accept two equal adjacent keys.

Preorder's first element is the root → 6. In the inorder list, everything left of 6 is the left subtree $\{2,4\}$, everything right is the right subtree $\{8\}$.

• Recurse left on inorder $2,4$ with the next preorder items $4,2$: root 4, left child 2.
• Recurse right on inorder $8$: single node 8.

      6
     / \
    4   8
   /
  2

Check: inorder $=2,4,6,8$ ✓. Why it works: inorder splits left/right around each root; preorder hands us the roots top-down. Together they pin down a unique tree.

Inorder P $=1,4,7$; inorder Q $=2,4,6$. Merge like the merge step of mergesort (this is the Binary Search / sorted-array world): $1,2,4,6,7$ (the two 4's collapse to one). A two-pointer merge of lists of size $m$ and $n$ does at most $m+n-1=3+3-1=5$ comparisons. Why inorder first? It converts each tree into a sorted list for free, so the hard part (sorting) is already done.

The successor of a node is the smallest key in its right subtree (if it has one).

• Node 8 has right subtree rooted at 10; its smallest key is the leftmost node there = 10.
• Node 6 has no right child, so its successor is the lowest ancestor whose left subtree contains 6: climbing 6 → 3 → 8, the first turn that is a "left" step is 3 being the left child of 8, so the successor is 8.

Cross-check with the sorted list $1,3,6,8,10,14$: after 8 comes 10 ✓, after 6 comes 8 ✓.

Use Structural Induction on the tree.

Base case. Empty tree or single node: vacuously/trivially a BST. ✓

Inductive hypothesis. Assume every proper subtree whose inorder is strictly increasing is itself a BST.

Inductive step. Let $T$ have root $r$, left subtree $T_L$, right subtree $T_R$. The inorder of $T$ is $\underset{\text{block }L}{\underbrace{\text{inorder}(T_L)}}\Vert [r]\Vert \underset{\text{block }R}{\underbrace{\text{inorder}(T_R)}}$ Given this whole sequence is strictly increasing:

1. Block $L$ appears entirely before $r$, so every key in $T_L$ is $<r$.
2. Block $R$ appears entirely after $r$, so every key in $T_R$ is $>r$.
3. Block $L$ is strictly increasing (a contiguous slice of an increasing sequence), so by IH $T_L$ is a BST. Same for $T_R$.

Conditions (1)–(3) are exactly the BST definition at $r$, recursively satisfied. Hence $T$ is a BST. $■$

This is why validation-by-inorder is correct, not just a heuristic — it powers Validate BST.

The largest key is the rightmost node. Two cases for the second largest:

• Case A: if the largest (rightmost) node has a left subtree, the 2nd largest is the rightmost node of that left subtree.
• Case B: if the rightmost node has no left child, the 2nd largest is its parent.

Walk right from the root, keeping a parent pointer:

def second_largest(root):
    if root is None or (root.left is None and root.right is None):
        return None                 # fewer than 2 nodes
    parent, cur = None, root
    while cur.right:                # go to the largest
        parent, cur = cur, cur.right
    if cur.left:                    # Case A
        cur = cur.left
        while cur.right:
            cur = cur.right
        return cur.key
    return parent.key               # Case B

Only one root-to-leaf path is walked → $O(h)$ time, $O(1)$ space.

Tree A: rightmost is 14 (8 → 10 → 14), parent = 10. 14 has no left child → Case B → answer 10. Check against sorted list $1,3,6,8,10,14$: 2nd largest is 10 ✓.

Each new key is larger than all before it, so it becomes the right child of the previous — a right-skewed line (essentially a linked list):

1
 \
  2
   \
    3
     \
      4
       \
        5

Height $h=n-1=4$. Inorder is still $1,2,3,4,5$ (correct!), but the recursion/stack depth is $O(n)$, and search degrades to $O(n)$ per operation. Fix: a self-balancing tree (AVL / Red-Black) enforces $h=O(\log n)$, keeping traversal and search fast while preserving the exact same sorted inorder.