Recover Binary Search Tree (Two Nodes Swapped)

▶

Steps

setup

Initialize pointers and start at root

Initialize first, second, and prev pointers to None. Set current pointer to root node (value 1).

💡 Setting up pointers is essential to track nodes during traversal and detect violations.

Line:

first = second = prev = None
current = root

💡 We start traversal at the root with no nodes visited yet.

fill_cells

Current node has no left child, process current (1)

Current node (1) has no left child, so we check for violation with prev (None). No violation since prev is None. Update prev to current (1). Move current to right child (null).

💡 Nodes without left children are processed immediately in inorder traversal.

Line:

if not current.left:
    if prev and prev.val > current.val:
        ...
    prev = current
    current = current.right

💡 First node visited sets prev pointer for future comparisons.

fill_cells

Move current to left child (3) to find predecessor

Current is null, so we move current pointer to node 2 (value 3), the left child of root, to continue traversal.

💡 Morris traversal moves to left subtree to find inorder predecessor.

Line:

else:
    pred = current.left
    while pred.right and pred.right != current:
        pred = pred.right

💡 We prepare to find the inorder predecessor of current node 2.

fill_cells

Find predecessor of current (3)

Find the rightmost node in current's left subtree. Node 3 has no left child, so predecessor is null. We proceed to process current node.

💡 Predecessor helps create temporary threaded links for Morris traversal.

Line:

pred = current.left
while pred.right and pred.right != current:
    pred = pred.right

💡 When no left child, we can process current node immediately.

compare

Process current (3), no violation

Compare prev (1) and current (3). Since 1 < 3, no violation. Update prev to current (3). Move current to right child (3).

💡 We detect violations by checking if prev.val > current.val; none here means order is correct so far.

Line:

if prev and prev.val > current.val:
    if not first:
        first = prev
        second = current
    else:
        second = current
prev = current
current = current.right

💡 Prev pointer moves forward to track last visited node.

fill_cells

Current (3) has no left child, move to current (2)

Current node (3) has no left child, so we move current pointer to right child (node 3's right child is node 3, but this is a threaded link in Morris traversal). We detect threaded link and remove it, then move current to node 3's right child (2).

💡 Morris traversal uses threaded links to traverse without recursion or stack.

Line:

if not pred.right:
    pred.right = current
    current = current.left
else:
    pred.right = None
    ...

💡 Threaded links are temporary and must be removed to restore tree structure.

compare

Process current (2), detect violation

Current node (2) has no left child, so we compare prev (3) and current (2). Since 3 > 2, violation detected. Mark first violation nodes: first = prev (3), second = current (2). Update prev to current (2). Move current to right (null).

💡 Detecting violation identifies swapped nodes that break BST property.

Line:

if not current.left:
    if prev and prev.val > current.val:
        if not first:
            first = prev
            second = current
        else:
            second = current
    prev = current
    current = current.right

💡 First violation found between nodes 3 and 2.

insert

Traversal complete, swap values of first and second nodes

Traversal is complete. Swap the values of the first node (3) and second node (2) to fix the BST.

💡 Swapping values corrects the BST without changing tree structure.

Line:

first.val, second.val = second.val, first.val

💡 The BST property is restored by swapping the two incorrect node values.

reconstruct

Confirm final tree structure after swap

The values of the swapped nodes have been exchanged. The tree structure remains unchanged but now satisfies BST properties.

💡 Confirming the final tree state helps understand the effect of the swap operation.

💡 Swapping values restores the BST without altering the tree shape.

reconstruct

Final state: BST recovered

The BST property is restored. The tree now correctly represents [3,1,null,null,2].

💡 Final step confirms the algorithm's success in recovering the BST.

💡 The swapped nodes have been corrected, restoring BST order.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root):
    first = second = prev = None  # STEP 1: Initialize pointers
    current = root  # STEP 1
    while current:  # STEP 2-7: Traverse until current is None
        if not current.left:  # STEP 2,6: No left child, process current
            if prev and prev.val > current.val:  # STEP 6: Detect violation
                if not first:
                    first = prev  # STEP 6: Mark first violation
                    second = current
                else:
                    second = current
            prev = current  # STEP 2,6: Update prev
            current = current.right  # STEP 2,6: Move right
        else:  # STEP 3-5: Find predecessor
            pred = current.left  # STEP 3
            while pred.right and pred.right != current:  # STEP 3
                pred = pred.right
            if not pred.right:  # STEP 4: Create threaded link
                pred.right = current
                current = current.left
            else:  # STEP 5: Remove threaded link and process current
                pred.right = None
                if prev and prev.val > current.val:  # STEP 6
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
    first.val, second.val = second.val, first.val  # STEP 7: Swap values

📊

Recover Binary Search Tree (Two Nodes Swapped) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the Morris traversal avoids extra space and how the swapped nodes are identified by violations in inorder sequence.

Current node: 1

132

132

Current node: 2

132

Current node: 2

132

Current node: 3

132

Current node: 3

132

132

312

312

312

Return: "[3,1,null,null,2]"

Key Takeaways

✓ Morris inorder traversal allows O(1) space traversal by temporarily modifying tree links.

This is hard to see from code alone because the threaded links are subtle and invisible without visualization.

✓ Violations in inorder sequence (prev.val > current.val) identify the two swapped nodes.

Visualizing the comparisons clarifies how the algorithm detects exactly which nodes to swap.

✓ Swapping values of the two identified nodes restores the BST without changing tree structure.

Seeing the final swap in the tree confirms the correctness of the approach beyond just code logic.

Practice

1. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

2. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

A. O(n log n) due to sorting nodes during traversal

B. O(n) because inorder traversal and balanced rebuild each take linear time

C. O(n^2) because rebuilding the tree involves repeated subtree constructions

D. O(n) for traversal but O(n log n) for balanced tree construction

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once -> O(n).

2. Step 2: Analyze balanced BST construction time

   Rebuilding uses indices to pick middle nodes without extra sorting -> O(n).

3. Step 3: Consider sorting complexity

   Although inorder traversal produces sorted nodes, if sorting is mistakenly applied, complexity becomes O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting nodes during traversal leads to O(n log n) [Trap]

Hint: Beware of sorting overhead; if sorting is done, complexity is O(n log n)

Common Mistakes:

• Assuming sorting is not needed, leading to O(n)
• Thinking recursive rebuild is O(n^2) due to repeated subtree calls
• Confusing traversal and construction complexities

3. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

4. The following code attempts to convert a BST to a Greater Tree using reverse inorder traversal. Identify the line that contains a subtle bug causing incorrect node values.

medium

A. Line 8: node = node.left instead of node = node.right

B. Line 6: while node: loop condition

C. Line 10: acc_sum += node.val accumulation

D. Line 12: node = node.right traversal after updating node

Solution

1. Step 1: Understand traversal order needed

   Reverse inorder traversal requires visiting right subtree first to accumulate greater values.

2. Step 2: Identify incorrect subtree traversal

   Line 8 incorrectly moves to left child first, reversing traversal order and causing wrong sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing node = node.left to node = node.right fixes traversal order [OK]

Hint: Reverse inorder must traverse right subtree first [OK]

Common Mistakes:

• Swapping left and right subtree traversal order
• Resetting acc_sum inside loops
• Updating node values before traversing right subtree

5. Suppose the BST can contain duplicate values and you want to find if there exist two nodes (not necessarily distinct) whose values sum to k. Which modification to the optimal inorder + two-pointer approach correctly handles this scenario?

hard

A. Perform inorder traversal and remove duplicates before applying two-pointer technique.

B. Use the same two-pointer approach but allow left and right pointers to point to the same index.

C. Use a hash set to store values and check complements, ignoring duplicates.

D. During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST.

Solution

1. Step 1: Understand duplicates and two-pointer constraints

   Two-pointer approach requires two distinct indices; if pointers meet, need to verify if duplicate values exist.

2. Step 2: Modify check when left == right

   Check if the value at that index occurs at least twice in the BST to allow sum with itself.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST. correctly handles duplicates without breaking two-pointer logic [OK]

Hint: Check duplicates count when pointers meet [OK]

Common Mistakes:

• Allowing pointers to be equal without duplicate check
• Removing duplicates loses valid pairs
• Ignoring duplicates in hash set approach