Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Move from brute-force thinking to an efficient approach using tree strategy.
You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2] Output: [2,1,4,null,null,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
[2, 1000].-231 <= Node.val <= 231 - 1O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?Problem summary: You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[1,3,null,null,2]
[3,1,4,null,null,2]
class Solution {
private TreeNode first, second, prev;
public void recoverTree(TreeNode root) {
inorder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev != null && prev.val > node.val) {
if (first == null) first = prev;
second = node;
}
prev = node;
inorder(node.right);
}
}
func recoverTree(root *TreeNode) {
var first, second, prev *TreeNode
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
if prev != nil && prev.Val > node.Val {
if first == nil {
first = prev
}
second = node
}
prev = node
inorder(node.Right)
}
inorder(root)
first.Val, second.Val = second.Val, first.Val
}
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
first = second = prev = None
def inorder(node: Optional[TreeNode]) -> None:
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev
second = node
prev = node
inorder(node.right)
inorder(root)
first.val, second.val = second.val, first.val
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn recover_tree(root: &mut Option<Rc<RefCell<TreeNode>>>) {
fn collect(node: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
if let Some(n) = node {
let left = n.borrow().left.clone();
collect(&left, vals);
vals.push(n.borrow().val);
let right = n.borrow().right.clone();
collect(&right, vals);
}
}
fn fix(node: &Option<Rc<RefCell<TreeNode>>>, sorted: &Vec<i32>, idx: &mut usize) {
if let Some(n) = node {
let left = n.borrow().left.clone();
fix(&left, sorted, idx);
let cur_val = n.borrow().val;
if cur_val != sorted[*idx] {
n.borrow_mut().val = sorted[*idx];
}
*idx += 1;
let right = n.borrow().right.clone();
fix(&right, sorted, idx);
}
}
let mut vals = Vec::new();
collect(root, &mut vals);
let mut sorted = vals.clone();
sorted.sort();
let mut idx = 0usize;
fix(root, &sorted, &mut idx);
}
}
function recoverTree(root: TreeNode | null): void {
let first: TreeNode | null = null;
let second: TreeNode | null = null;
let prev: TreeNode | null = null;
const inorder = (node: TreeNode | null): void => {
if (!node) return;
inorder(node.left);
if (prev && prev.val > node.val) {
if (!first) first = prev;
second = node;
}
prev = node;
inorder(node.right);
};
inorder(root);
if (first && second) {
[first.val, second.val] = [second.val, first.val];
}
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.