How do you solve Recover Binary Search Tree on LeetCode?

Recover Binary Search Tree (LeetCode #99) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: In-order traversal of a BST gives sorted values.

What is the brute force solution for Recover Binary Search Tree?

The brute force approach for Recover Binary Search Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves traversing the tree to find the two swapped nodes by checking all pairs of nodes. This is straightforward but inefficient, as it requires multiple passes through the tree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Recover Binary Search Tree?

Recover Binary Search Tree uses the following concepts: Tree, Depth-First Search, Binary Search Tree, Binary Tree. The recommended patterns to study are: In-order Traversal, Tree Traversal.

What are the interview tips for Recover Binary Search Tree?

Always clarify the problem statement and constraints before diving into coding. Think about the properties of a BST and how they can help simplify the problem. Practice explaining your thought process as you code to simulate the interview environment.

What are common mistakes when solving Recover Binary Search Tree?

Not considering edge cases where the swapped nodes are adjacent. Failing to properly track the previous node during traversal.

#99

Recover Binary Search Tree

Medium

TreeDepth-First SearchBinary Search TreeBinary TreeIn-order TraversalTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses an in-order traversal to identify the swapped nodes in a single pass while keeping track of the previous node. This approach is efficient and uses constant space.

⚙️

Algorithm

3 steps

1Step 1: Initialize pointers for the previous node, first node, and second node.
2Step 2: Perform an in-order traversal of the tree, updating the previous node and checking for swapped nodes.
3Step 3: Swap the values of the identified nodes.

solution.py22 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def recoverTree(self, root: TreeNode) -> None:
9        self.first = self.second = self.prev = None
10        def inorder(node):
11            if not node:
12                return
13            inorder(node.left)
14            if self.prev and self.prev.val > node.val:
15                if not self.first:
16                    self.first = self.prev
17                self.second = node
18            self.prev = node
19            inorder(node.right)
20
21        inorder(root)
22        self.first.val, self.second.val = self.second.val, self.first.val

ℹ

Complexity note: The time complexity is O(n) because we traverse each node exactly once. The space complexity is O(1) since we only use a few pointers, independent of the input size.

1In-order traversal of a BST gives sorted values.
2Only two nodes are swapped, so we only need to find those two nodes.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.