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. You are given a sorted array of unique integers and need to construct a binary search tree with minimal height. Which approach guarantees the resulting tree is height-balanced and constructed in O(n) time?

easy

A. Use a divide-and-conquer recursion that picks the middle element as root and recursively builds left and right subtrees.

B. Insert elements one by one into an empty BST using standard BST insertion.

C. Use a greedy approach that always inserts the smallest remaining element as the left child.

D. Build a balanced BST by repeatedly merging two smaller balanced BSTs.

Solution

1. Step 1: Understand the problem constraints

   The input is a sorted array, and the goal is to build a height-balanced BST efficiently.

2. Step 2: Evaluate approaches

   Inserting elements one by one leads to skewed trees and O(n^2) time. Greedy insertion of smallest elements does not guarantee balance. Merging BSTs is not straightforward and inefficient. The divide-and-conquer approach picks the middle element as root, ensuring balanced subtrees and O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Middle element chosen recursively -> balanced BST in O(n) time [OK]

Hint: Middle element recursion ensures balanced BST [OK]

Common Mistakes:

• Thinking inserting one by one is efficient
• Assuming greedy insertion balances tree

2. 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

3. 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

4. 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

5. What is the time complexity of the iterative inorder traversal approach to find the kth smallest element in a BST, where H is the height of the tree and k is the input parameter?

medium

A. O(H + k), where H is the height of the tree and k is the kth element to find

B. O(k), since only k nodes are visited

C. O(k log n), assuming balanced BST

D. O(n), where n is the total number of nodes in the BST

Solution

1. Step 1: Analyze traversal steps

   The algorithm traverses down to the leftmost node (cost O(H)) and then visits k nodes in inorder sequence.

2. Step 2: Combine costs

   Total time is O(H) to reach leftmost node plus O(k) to visit k nodes, so O(H + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal cost depends on height plus k nodes visited [OK]

Hint: Traversal cost includes height plus k nodes visited [OK]

Common Mistakes:

• Assuming O(n) always
• Ignoring height cost
• Assuming only k nodes visited without stack overhead