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. Given the following code for inserting a value into a BST, what will be the value of the variable parent.val when inserting 5 into the BST rooted at 4 with left child 2 and right child 7?

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

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
val = 5
insertIntoBST(root, val)

easy

A. 4

B. 7

C. 2

D. 5

Solution

1. Step 1: Trace insertion path

   Start at root (4). Since 5 > 4, move right to node 7. Update parent to 4.

2. Step 2: Check right child of 7

   5 < 7, so move left. Left child of 7 is None, so insert here. Parent is now 7, but last parent before insertion was 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Parent is last non-null node before insertion -> 4 [OK]

Hint: Parent tracks last node before insertion point [OK]

Common Mistakes:

• Confusing parent with current node
• Off-by-one in loop iteration
• Mistaking inserted value as parent

2. Consider the following code for finding the lowest common ancestor in a BST. Given the BST below and nodes p=2 and q=8, what value does the function return? BST structure: 6 / \ 2 8 / \ \ 0 4 9 / \ 3 5

easy

A. 2

B. 8

C. 4

D. 6

Solution

1. Step 1: Trace first iteration with current=6

   p=2 and q=8; 2 < 6 and 8 > 6, so current is split point; return 6.

2. Step 2: Confirm no further traversal

   Since p and q lie on different sides of 6, 6 is the LCA.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Split point found at root 6 immediately [OK]

Hint: LCA is where paths to p and q diverge [OK]

Common Mistakes:

• Returning smaller node instead of split point
• Confusing left/right subtree traversal
• Off-by-one error in loop conditions

3. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

4. Consider the following buggy code snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

5. Consider the following buggy code for deleting a node in a BST. Which line contains the subtle bug that can cause the BST property to break when deleting a node with two children?

def deleteNode(root, key):
    if not root:
        return null
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            successor = findSuccessor(root)
            root.val = successor.val
            root.left = deleteNode(root.right, successor.val)  # Bug here
    return root

medium

A. Line where root.left is assigned deleteNode(root.right, successor.val)

B. Line where root.left is assigned deleteNode(root.left, key)

C. Line where root.val is set to successor.val

D. Line where root.right is assigned deleteNode(root.right, key)

Solution

1. Step 1: Identify two-children deletion logic

   When deleting a node with two children, we replace its value with the successor's value and then delete the successor from the right subtree.

2. Step 2: Spot incorrect subtree assignment

   The line assigns root.left = deleteNode(root.right, successor.val), which incorrectly deletes from the right subtree but assigns result to left child, breaking BST structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct line should assign root.right = deleteNode(root.right, successor.val) [OK]

Hint: Deleting successor must update right subtree, not left [OK]

Common Mistakes:

• Mixing left and right subtree assignments
• Forgetting to update parent's child pointer
• Replacing value but not deleting successor