Recover Binary Search Tree (Two Nodes Swapped)

📋

Recover Binary Search Tree (Two Nodes Swapped)

Edge cases:

</>

IDE

def recoverTree(root: TreeNode) -> None:public void recoverTree(TreeNode root)void recoverTree(TreeNode* root)function recoverTree(root)

def recoverTree(root):
    # Write your solution here
    pass

class Solution {
    public void recoverTree(TreeNode root) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void recoverTree(TreeNode* root) {
    // Write your solution here
}

function recoverTree(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Tree unchanged despite swapped nodesFailed to detect any violation in inorder traversal; no nodes swapped.✅ Track previous node during inorder traversal and identify nodes where current.val < prev.val.

Wrong: Swapped wrong nodes or partial fixOnly detected one violation or swapped incorrect nodes.✅ Store both first and second violation nodes and swap their values after traversal.

Wrong: Crashes or errors on empty or single-node treesNo null checks or base case handling.✅ Add base case checks for null root and single node trees before processing.

Wrong: Time limit exceeded on large inputsUsing sorting or inefficient traversal causing O(n log n) or worse time.✅ Use O(n) inorder traversal with two pointers or Morris traversal for O(1) space.

✓

Test Cases

Try testing your solution on empty and single-node trees to catch base case bugs.

Focus on detecting both one and two violations in inorder traversal for swapped nodes.

Optimize your traversal to avoid sorting and reduce space complexity.

t1_01basic

Input{"root":[1,3,null,null,2]}

Expected[3,1,null,null,2]

⏱ Performance - must finish in 2000ms

The nodes with values 1 and 2 are swapped. After recovery, the BST property is restored.

💡 Recall that inorder traversal of a BST should produce a sorted sequence.

💡 Identify the two nodes where the inorder sequence deviates from sorted order.

💡 Swap the values of the two identified nodes to restore BST property.

Why it failed: Failed to detect swapped nodes correctly; likely missed one or both nodes causing incorrect swap. Fix by tracking two nodes where inorder order is violated.

✓ Correctly identified and swapped the two nodes restoring BST property.

t1_02basic

Input{"root":[3,1,4,null,null,2]}

Expected[2,1,4,null,null,3]

⏱ Performance - must finish in 2000ms

Nodes with values 2 and 3 are swapped. After recovery, the BST property is restored.

💡 Perform inorder traversal and look for violations in the sorted order.

💡 Two violations may indicate swapped nodes far apart in inorder sequence.

💡 Swap the values of the two nodes identified at the violations.

Why it failed: Incorrect recovery due to missing second violation or swapping wrong nodes. Fix by tracking both first and second nodes where inorder order breaks.

✓ Successfully handled non-adjacent swapped nodes and restored BST.

t2_01edge

Input{"root":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree input; no nodes to swap or recover.

💡 Check if the tree is empty before processing.

💡 Handle null or empty root as a base case.

💡 Return immediately if root is None to avoid errors.

Why it failed: Code crashes or errors on empty input due to missing null check. Fix by adding base case for empty tree.

✓ Correctly handles empty tree without errors.

t2_02edge

Input{"root":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node tree; no swaps needed.

💡 A single node tree is always a valid BST.

💡 No swaps possible or needed with one node.

💡 Return the tree as is without modification.

Why it failed: Incorrectly modifies single node tree or crashes. Fix by handling single node as base case with no action.

✓ Correctly returns single node tree unchanged.

t2_03edge

Input{"root":[2,3]}

Expected[3,2]

⏱ Performance - must finish in 2000ms

Two nodes swapped at root and left child; must swap back.

💡 Inorder traversal of two nodes swapped will show one violation.

💡 Identify the two nodes and swap their values.

💡 Check boundary conditions when tree has only two nodes.

Why it failed: Fails to swap nodes when tree has only two nodes. Fix by ensuring code handles minimal tree sizes correctly.

✓ Successfully swaps two nodes in minimal tree.

t2_04edge

Input{"root":[2,2,2]}

Expected[2,2,2]

⏱ Performance - must finish in 2000ms

All nodes identical; no swaps needed and BST property trivially holds.

💡 Check if all node values are identical.

💡 Inorder traversal will be constant sequence with no violations.

💡 Return tree unchanged if no violations found.

Why it failed: Incorrectly swaps or modifies tree with identical values. Fix by verifying uniqueness or no violations before swapping.

✓ Correctly handles tree with identical values without modification.

t3_01corner

Input{"root":[5,3,9,2,7,6,10]}

Expected[5,3,9,2,7,6,10]

⏱ Performance - must finish in 2000ms

No nodes swapped; tree is already a valid BST.

💡 Check if the tree is already a valid BST before swapping.

💡 Inorder traversal should be strictly increasing with no violations.

💡 If no violations found, do not modify the tree.

Why it failed: Incorrectly swaps nodes when none are swapped. Fix by verifying if any violations exist before swapping.

✓ Correctly identifies no swaps needed and leaves tree unchanged.

t3_02corner

Input{"root":[6,3,8,1,4,7,9,null,null,5]}

Expected[6,3,8,1,5,7,9,null,null,4]

⏱ Performance - must finish in 2000ms

Swapped nodes 4 and 5 are adjacent in inorder traversal; simple swap fixes tree.

💡 Adjacent swapped nodes cause a single violation in inorder traversal.

💡 Track the first and second nodes where order breaks.

💡 Swap their values to fix the BST.

Why it failed: Fails to handle adjacent swapped nodes correctly, possibly swapping wrong nodes. Fix by careful tracking of first and second violation nodes.

✓ Correctly recovers BST with adjacent swapped nodes.

t3_03corner

Input{"root":[10,5,15,2,7,12,20,null,null,null,null,11,13]}

Expected[10,5,15,2,7,13,20,null,null,null,null,11,12]

⏱ Performance - must finish in 2000ms

Swapped nodes 12 and 13 are far apart in inorder traversal; requires identifying two violations.

💡 Non-adjacent swapped nodes cause two violations in inorder traversal.

💡 Track both first and second violation nodes carefully.

💡 Swap their values to restore BST property.

Why it failed: Fails to detect second violation or swaps wrong nodes. Fix by storing both violation nodes and swapping their values.

✓ Correctly recovers BST with non-adjacent swapped nodes.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1,50001,75001,12501,37501,62501,87501,6251,18751,31251,43751,56251,68751,81251,93751,3126,9376,15626,21876,28126,34376,40626,46876,53126,59376,65626,71876,78126,84376,90626,96876,2,50002,75002,12502,37502,62502,87502,6252,18752,31252,43752,56252,68752,81252,93752,3127,9377,15627,21877,28127,34377,40627,46877,53127,59377,65627,71877,78127,84377,90627,96877,3,50003,75003,12503,37503,62503,87503,6253,18753,31253,43753,56253,68753,81253,93753,3128,9378,15628,21878,28128,34378,40628,46878,53128,59378,65628,71878,78128,84378,90628,96878,4,50004,75004,12504,37504,62504,87504,6254,18754,31254,43754,56254,68754,81254,93754,3129,9379,15629,21879,28129,34379,40629,46879,53129,59379,65629,71879,78129,84379,90629,96879,5,50005,75005,12505,37505,62505,87505,6255,18755,31255,43755,56255,68755,81255,93755,3130,9380,15630,21880,28130,34380,40630,46880,53130,59380,65630,71880,78130,84380,90630,96880,6,50006,75006,12506,37506,62506,87506,6256,18756,31256,43756,56256,68756,81256,93756,3131,9381,15631,21881,28131,34381,40631,46881,53131,59381,65631,71881,78131,84381,90631,96881,7,50007,75007,12507,37507,62507,87507,6257,18757,31257,43757,56257,68757,81257,93757,3132,9382,15632,21882,28132,34382,40632,46882,53132,59382,65632,71882,78132,84382,90632,96882,8,50008,75008,12508,37508,62508,87508,6258,18758,31258,43758,56258,68758,81258,93758,3133,9383,15633,21883,28133,34383,40633,46883,53133,59383,65633,71883,78133,84383,90633,96883,9,50009,75009,12509,37509,62509,87509,6259,18759,31259,43759,56259,68759,81259,93759,3134,9384,15634,21884,28134,34384,40634,46884,53134,59384,65634,71884,78134,84384,90634,96884,10,50010,75010,12510,37510,62510,87510,6260,18760,31260,43760,56260,68760,81260,93760,3135,9385,15635,21885,28135,34385,40635,46885,53135,59385,65635,71885,78135,84385,90635,96885]}

Expectednull

⏱ Performance - must finish in 2000ms

Large BST with n=100 nodes; O(n) or O(n log n) solution must complete within 2 seconds.

💡 Use inorder traversal with O(n) time complexity.

💡 Avoid sorting or extra space beyond O(h).

💡 Consider Morris traversal for O(1) space.

Why it failed: Solution exceeds time limit due to inefficient traversal or sorting. Fix by using O(n) inorder traversal with constant or O(h) space.

✓ Solution runs within time limit using efficient inorder traversal.

Practice

1. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    # BUG: Missing restoration of thread
                    self.next_val = self.current.val
                    self.current = self.current.right

medium

A. Line resetting pre.right to null is missing, so threads are not removed.

B. Line setting self.next_val = self.current.val is incorrect and should be removed.

C. Line moving self.current to self.current.left should be self.current.right instead.

D. Line initializing self.current = root in __init__ is incorrect and should be null.

Solution

1. Step 1: Identify thread restoration step

   In Morris traversal, after visiting a node, the temporary thread (pre.right) must be reset to null to restore the tree.

2. Step 2: Locate missing restoration

   The code omits resetting pre.right = None in the else block, causing the tree to remain modified after iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing thread removal corrupts tree structure [OK]

Hint: Always restore threads to avoid tree corruption [OK]

Common Mistakes:

• Forgetting to remove threads
• Misplacing next_val assignment
• Incorrect current pointer updates

2. What is the worst-case time complexity of inserting a value into a binary search tree using the iterative insertion method shown below?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while 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

medium

A. O(1) because insertion is done at a leaf immediately

B. O(h) where h is the height of the tree, since traversal down the tree is needed

C. O(n) where n is the number of nodes, because all nodes might be visited

D. O(log n) always, because BSTs are balanced by definition

Solution

1. Step 1: Identify traversal cost

   Insertion requires traversing from root down to a leaf where the new node is inserted.

2. Step 2: Relate traversal to tree height

   In worst case, the tree is skewed, so height h can be up to n, but complexity is expressed as O(h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Traversal cost dominates insertion -> O(h) [OK]

Hint: Insertion cost depends on tree height, not always balanced [OK]

Common Mistakes:

• Assuming O(1) because insertion is at leaf
• Confusing height h with number of nodes n
• Assuming BST is always balanced

3. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space

4. Suppose the BST can contain duplicate values, and you want to find the lowest common ancestor of two nodes p and q that may have the same value. Which modification to the optimal iterative algorithm correctly handles duplicates while maintaining efficiency?

hard

A. Define a consistent rule that duplicates go to the right subtree and use original algorithm without changes.

B. Modify comparisons to use '<=' and '>=' to ensure traversal includes duplicates on both sides.

C. Augment each node with a count of duplicates and traverse left or right based on counts to find LCA.

D. Store paths from root to p and q and compare them to find LCA, since BST property is ambiguous with duplicates.

Solution

1. Step 1: Understand duplicate handling in BST

   BSTs with duplicates require a consistent insertion rule, commonly duplicates go to right subtree.

2. Step 2: Modify comparisons to include duplicates

   Using '<=' and '>=' in comparisons ensures traversal includes duplicates correctly on both sides.

3. Step 3: Avoid ambiguous or inefficient methods

   Path comparison or augmenting nodes adds overhead and complexity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Inclusive comparisons handle duplicates while preserving efficiency [OK]

Hint: Modify comparison operators to handle duplicates correctly [OK]

Common Mistakes:

• Using strict comparisons that miss duplicates
• Reverting to path comparison losing efficiency
• Adding unnecessary data structures

5. Suppose the BST can contain duplicate values, and you want to find all nodes with a given value. Which modification to the optimal iterative search algorithm correctly finds all such nodes?

hard

A. Stop at the first found node and return it, since duplicates are not allowed in BSTs.

B. Modify the search to continue searching both left and right subtrees even after finding a matching node.

C. Traverse the entire tree recursively to collect all nodes with the target value, ignoring BST property.

D. Use a queue to perform BFS and collect all nodes with the target value efficiently.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on either left or right subtree depending on BST definition.

2. Step 2: Modify search to find all matches

   After finding a node with val, continue searching both subtrees to find all duplicates.

3. Step 3: Avoid full traversal

   Using BST property to prune search still possible by checking subtrees where duplicates may exist.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Continuing search after first match finds all duplicates [OK]

Hint: Duplicates require searching both subtrees after match [OK]

Common Mistakes:

• Stopping at first match or ignoring BST property completely