Recover Binary Search Tree

MEDIUM

Description

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:

The number of nodes in the tree is in the range [2, 1000].
-2³¹ <= Node.val <= 2³¹ - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Approaches

Checkout 4 different approaches to solve Recover Binary Search Tree. Click on different approaches to view the approach and algorithm in detail.

In-order Traversal and Sort

A straightforward but less efficient approach is to perform an in-order traversal of the tree, store all the node values in a list, sort the list to get the correct order, and then iterate through the tree again (or a list of nodes from the first traversal) to update the node values with the sorted ones.

Algorithm

Create two lists: one to store TreeNode objects (nodes) and another for their values (vals).
Perform an in-order traversal of the BST. In the traversal, add each visited node to the nodes list and its value to the vals list.
After the traversal, the nodes list contains all nodes in in-order sequence, but the vals list is out of order due to the swap.
Sort the vals list. This gives the correct sequence of values for a valid BST.
Iterate from i = 0 to n-1, where n is the number of nodes. For each i, update the value of the node at nodes.get(i) with the value from the sorted list vals.get(i). This restores the BST property.

This method relies on the fundamental property of a BST: an in-order traversal yields sorted values. By capturing the node references and their values, we can correct the tree by sorting the values and reassigning them to the nodes in their correct in-order positions.

public void recoverTree(TreeNode root) {
    List<TreeNode> nodes = new ArrayList<>();
    List<Integer> vals = new ArrayList<>();
    inorderTraversal(root, nodes, vals);
    Collections.sort(vals);
    for (int i = 0; i < nodes.size(); i++) {
        nodes.get(i).val = vals.get(i);
    }
}

private void inorderTraversal(TreeNode node, List<TreeNode> nodes, List<Integer> vals) {
    if (node == null) {
        return;
    }
    inorderTraversal(node.left, nodes, vals);
    nodes.add(node);
    vals.add(node.val);
    inorderTraversal(node.right, nodes, vals);
}

Complexity Analysis

Time Complexity: O(N log N)Space Complexity: O(N)

Pros and Cons

Pros:

Conceptually simple and easy to understand.
Easy to implement correctly.

Cons:

Has a suboptimal time complexity of O(N log N) due to sorting.
Uses O(N) extra space, which can be inefficient for very large trees.
It reassigns values to all nodes, which is unnecessary as only two nodes are incorrect.

Code Solutions

Checking out 5 solutions in different languages for Recover Binary Search Tree. Click on different languages to view the code.

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private TreeNode prev , first , second ; public void RecoverTree ( TreeNode root ) { dfs ( root ); int t = first . val ; first . val = second . val ; second . val = t ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); if ( prev != null && prev . val > root . val ) { if ( first == null ) { first = prev ; } second = root ; } prev = root ; dfs ( root . right ); } }

Video Solution

Watch the video walkthrough for Recover Binary Search Tree

Algorithms:

Depth-First Search

Data Structures:

TreeBinary TreeBinary Search Tree

Companies:

Amazon |Apple |Bloomberg |Microsoft |