99. Recover Binary Search Tree

MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Problem Description

In this problem, we have a binary search tree (BST) that has had the values of exactly two of its nodes swapped by mistake. Our task is to recover this BST, which means we need to find these two nodes and swap their values back to their correct positions. It is important to note that we should achieve this without altering the structure of the tree; only the values of the nodes should be swapped back.

Flowchart Walkthrough

To analyze the appropriate algorithm for Leetcode 99. Recover Binary Search Tree, let's navigate through the algorithm using the Flowchart. Here's a detailed step-by-step analysis:

Is it a graph?

Yes: Although implicitly in this scenario, the binary search tree can be considered a graph where each node has edges connecting to its children.

Is it a tree?

Yes: As the problem specifically involves a binary search tree, which is a subtype of a tree, we affirm it as a tree.

Now that we've identified that the data structure involved is a tree, the flowchart directs us to utilize Depth-First Search (DFS) to solve problems involving trees unless otherwise indicated by additional problem constraints or goals. In the case of recovering a binary search tree, DFS is suitable as it allows in-depth examination and manipulation of nodes, crucial for identifying and correcting mispositioned nodes.

Conclusion: According to the decision path in the flowchart that advises on using DFS for tree problems, Depth-First Search is the optimal choice for solving the problem of recovering a binary search tree as it efficiently explores tree structures.

Intuition

To solve this problem, we should first understand what a binary search tree is. A BST is a tree structure where the left child's value of a node is less than the node's value, and the right child's value is greater than the node's value. This property must be true for all nodes in the BST.

Given this property, if two nodes' values are swapped, it violates the tree's ordering rule. Specifically, there will be a pair of consecutive nodes in an in-order traversal of the BST where the first node's value is greater than the second node's value, which should not happen in a correctly ordered BST.

The solution approach uses an in-order traversal, which visits the nodes of the BST in ascending order of their values. During the traversal, we can find the two nodes that are out of order. The dfs function recursively traverses the tree in-order and uses three non-local variables prev, first, and second. These help to track the previous node visited and the two nodes that are out of order.

prev keeps track of the previous node in the in-order traversal.
first will be assigned to the first node that appears in the wrong order.
second will be updated to the subsequent node that appears in the wrong order.

As we traverse the tree, whenever we find a node whose value is less than the value of the prev node, we know we've encountered an anomaly:

If it's the first anomaly, we assign prev to first.
If it's the second anomaly, we assign the current node to second.

After the traversal, first and second will be the two nodes that need their values swapped. The last line of the solution swaps the values of these two nodes.

While there could be more than one pair of nodes which appear to be out of order due to the swap, it's guaranteed that swapping first and second will correct the BST because the problem states that exactly two nodes have been swapped. Thus the solution correctly recovers the BST by swapping the values of first and second.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation of the solution utilizes a depth-first search algorithm, which is a standard approach to traverse and search all the nodes in a tree. This search pattern is essential for checking each node and its value relative to the BST's ordering properties while maintaining a manageable complexity. Here's a step-by-step explanation of how the implemented code works:

In-Order Traversal: The core of the solution relies on an in-order traversal. In a BST, an in-order traversal visits nodes in a sorted order. If two nodes are swapped, the order will be disrupted, and we can identify those nodes during this traversal.
Recursive Depth-First Search (DFS): We define the dfs function, which is a recursive function that performs the in-order traversal of the tree. It visits the left child, processes the current node, and then visits the right child.
Using Non-Local Variables: We use non-local variables prev, first, and second to keep track of the previous node, the first out-of-order node, and the second out-of-order node, respectively. Non-local variables are needed because they maintain their values between recursive calls.
Identifying Out-of-Order Nodes: As we perform the in-order traversal, whenever we encounter a node that has a value less than the prev node, this indicates an anomaly in the ordering. The first anomaly is when we set the prev as the first, and the next anomaly detected involves setting second as the current node with the lesser value.
Swapping Values: After the in-order traversal, we have isolated the two nodes that were incorrectly swapped. To fix the BST, we simply need to swap their values. This is done in the last line of the recoverTree method by the expression first.val, second.val = second.val, first.val.

Here is what the code does, broken down by each line:

prev = first = second = None: Initialize variables to None. prev will track the most recent node during in-order traversal, while first and second will track the two nodes that need to be swapped.
dfs(root): Start the DFS in-order traversal from the root of the tree.
if root is None: return: If the current node is None, backtrack since it's the base case for the recursion.
dfs(root.left): Recursively traverse the left subtree, which will visit all nodes smaller than the current node before it processes the current node.
if prev and prev.val > root.val: Check if the current node (root) has a value less than that of prev, which would indicate a violation of the BST properties.
if first is None: first = prev: If first is not set, it means this is the first anomaly found, and we set first to prev.
second = root: Whether the current anomaly is the first or subsequent, update second to the current node (root).
prev = root: Update prev to the current node (root) as it is now the most recent node visited.
dfs(root.right): Recursively traverse the right subtree, which will visit all nodes greater than the current node.

Using this approach, we ensure the issue is corrected without disrupting the tree's structure, and the time complexity is O(N), where N is the number of nodes in the tree, because each node is visited exactly once during the in-order traversal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have a binary search tree with the following in-order traversal before any nodes have been swapped:

1, 2, 3, 4, 5, 6, 7

Now, let's say the values at nodes 3 and 5 have been swapped by mistake. The in-order traversal of the BST will now look like this:

1, 2, 5, 4, 3, 6, 7

We can see that the series is mostly ascending except for two points where the order is disrupted. Specifically, 5 appears before 4 and 3 appears after 4, which is not correct according to BST properties.

We start the depth-first search with these steps:

Initialize prev, first, and second as None.
Perform in-order traversal starting at the root.
Traverse to the left-most node, updating prev as we go along.
Once we reach the node with value 2, we traverse up and then right, encountering 5. This is where we first notice the order is incorrect since 5 > 2, but prev is None, so we move on.
Next, we traverse to 4. Here we find prev.val (which is 5) > root.val (which is 4). This is our first anomaly, so we set first to prev (5) and leave second as None for now.
We continue our traversal. Now prev is set to 4. When we get to 3, we see that prev.val (4) > root.val (3). We've found our second anomaly. We assign second to the current node (3).
We finish the traversal by visiting the remaining nodes (6 and 7), but no further anomalies are found.

Now, we have our two nodes that were swapped: first (with value 5) and second (with value 3). The final step is to swap back their values. After swapping, the first node will hold the value 3 and the second node will hold the value 5.

By following these steps, we have successfully recovered the original BST:

1, 2, 3, 4, 5, 6, 7

This is how the given solution approach effectively corrects the binary search tree with a time complexity of O(N) by identifying and swapping the two nodes that have been mistakenly swapped.

Solution Implementation

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8class Solution:
9    def recoverTree(self, root: Optional[TreeNode]) -> None:
10        """
11        This function corrects a binary search tree (BST) where two nodes have been swapped by mistake.
12        It modifies the tree in-place without returning anything.
13        """
14
15        # Helper function to perform in-order traversal
16        def inorder_traversal(node):
17            # Base case: if the current node is None, do nothing
18            if node is None:
19                return
20          
21            # Using 'nonlocal' to modify the outside scope variables
22            nonlocal previous, first_swapped, second_swapped
23
24            # Traverse the left subtree
25            inorder_traversal(node.left)
26          
27            # Check if the previous node has greater value than the current node
28            # This indicates that the nodes are swapped
29            if previous and previous.val > node.val:
30                # If it's the first occurrence, update first_swapped
31                if first_swapped is None:
32                    first_swapped = previous
33                # Either way, update second_swapped to the current node
34                second_swapped = node
35          
36            # Update previous to the current node before moving to the right subtree
37            previous = node
38          
39            # Traverse the right subtree
40            inorder_traversal(node.right)
41
42        # Initialize the variables
43        previous = first_swapped = second_swapped = None
44      
45        # Start the in-order traversal
46        inorder_traversal(root)
47
48        # Swap the values of the two swapped nodes to recover the BST
49        first_swapped.val, second_swapped.val = second_swapped.val, first_swapped.val
50

1class Solution {
2    // Class member variables to keep track of previous, first and second nodes.
3    private TreeNode previousNode;
4    private TreeNode firstSwappedNode;
5    private TreeNode secondSwappedNode;
6
7    /**
8     * Initiates the recovery process of the binary search tree by calling the depth-first search method 
9     * and then swapping the values of the two nodes that were identified as incorrectly placed.
10     * 
11     * @param root The root of the binary tree that we are trying to recover.
12     */
13    public void recoverTree(TreeNode root) {
14        // Start in-order traversal to find the swapped nodes.
15        inOrderTraversal(root);
16      
17        // Swap the values of the identified nodes to correct the tree.
18        int temp = firstSwappedNode.val;
19        firstSwappedNode.val = secondSwappedNode.val;
20        secondSwappedNode.val = temp;
21    }
22
23    /**
24     * Performs an in-order traversal of the binary tree to identify the two nodes that are swapped.
25     * It assumes that we are dealing with a binary search tree where an in-order traversal
26     * would result in a sorted sequence of values.
27     * 
28     * @param node The current node being visited in the traversal.
29     */
30    private void inOrderTraversal(TreeNode node) {
31        // Base case: If the current node is null, return.
32        if (node == null) {
33            return;
34        }
35      
36        // Recursively traverse the left subtree.
37        inOrderTraversal(node.left);
38      
39        // Process current node: Compare current node's value with previous node's value.
40        if (previousNode != null && previousNode.val > node.val) {
41            // If this condition is true, a swapped node is found.
42            // If it's the first swapped node, assign previousNode to firstSwappedNode.
43            if (firstSwappedNode == null) {
44                firstSwappedNode = previousNode;
45            }
46            // Assign current node to secondSwappedNode.
47            secondSwappedNode = node;
48        }
49      
50        // Update previous node to the current node before moving to the right subtree.
51        previousNode = node;
52      
53        // Recursively traverse the right subtree.
54        inOrderTraversal(node.right);
55    }
56}
57
58/**
59 * Definition for a binary tree node.
60 */
61class TreeNode {
62    int val;
63    TreeNode left;
64    TreeNode right;
65
66    TreeNode() {}
67  
68    TreeNode(int val) {
69        this.val = val;
70    }
71
72    TreeNode(int val, TreeNode left, TreeNode right) {
73        this.val = val;
74        this.left = left;
75        this.right = right;
76    }
77}
78

1#include <functional> // Include the functional header for std::function
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    void recoverTree(TreeNode* root) {
16        TreeNode* previous = nullptr; // Pointer to keep track of the previous node during in-order traversal
17        TreeNode* first = nullptr;    // Pointer to the first node that is out of the expected order
18        TreeNode* second = nullptr;   // Pointer to the second node that is out of the expected order
19
20        // Function to perform in-order traversal and identify the two nodes that are out of order
21        std::function<void(TreeNode*)> inorderTraversal = [&](TreeNode* node) {
22            if (!node) return; // If the node is null, return from the function
23
24            inorderTraversal(node->left); // Traverse to the left child
25          
26            // Check if the previous node's value is greater than the current node's value
27            if (previous && previous->val > node->val) {
28                // If this is the first occurrence of an out-of-order pair, store the first node
29                if (!first) first = previous;
30                // In case of second occurrence or adjacent nodes being out of order, store the second node
31                second = node;
32            }
33            previous = node; // Update the previous pointer to the current node
34
35            inorderTraversal(node->right); // Traverse to the right child
36        };
37
38        inorderTraversal(root); // Start the in-order traversal from the root
39
40        if (first && second) {
41            // Swap the values of the first and second nodes to correct the tree
42            std::swap(first->val, second->val);
43        }
44    }
45};
46

1// Typing for a binary tree node
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Function to recover a binary search tree. Two of the nodes of the tree are swapped by mistake. 
10 * To correct this, we need to swap them back to their original position without changing the tree structure.
11 * This function modifies the tree in-place.
12 *
13 * @param {TreeNode | null} root - The root of the binary tree.
14 * @returns {void} Doesn't return anything and modifies the root in-place.
15 */
16function recoverTree(root: TreeNode | null): void {
17    let previous: TreeNode | null = null;
18    let firstSwappedNode: TreeNode | null = null;
19    let secondSwappedNode: TreeNode | null = null;
20
21    /**
22     * Depth-first traversal of the tree to find the two nodes that need to be swapped.
23     *
24     * @param {TreeNode | null} node - The current node to inspect in the DFS traversal.
25     */
26    function traverseAndFindSwappedNodes(node: TreeNode | null): void {
27        if (!node) {
28            return;
29        }
30        // Traverse the left subtree
31        traverseAndFindSwappedNodes(node.left);
32        // If the previous node's value is greater than the current node's value, we have found a swapped node
33        if (previous && previous.val > node.val) {
34            // The first swapped node is the one with a greater value than the one that should have been after it
35            if (firstSwappedNode === null) {
36                firstSwappedNode = previous; // Found first element that's out of order
37            }
38            // The second node is the current one, or the one that should have gone before the previous one
39            secondSwappedNode = node; // Found next element that's out of order
40        }
41        // Mark this node as the previous node for comparison in the next iteration
42        previous = node;
43        // Traverse the right subtree
44        traverseAndFindSwappedNodes(node.right);
45    }
46
47    // Start the in-order DFS traversal from the root
48    traverseAndFindSwappedNodes(root);
49  
50    if (firstSwappedNode && secondSwappedNode) {
51        // Swap the values of the first and second swapped nodes to correct the tree
52        [firstSwappedNode.val, secondSwappedNode.val] = [secondSwappedNode.val, firstSwappedNode.val];
53    }
54}
55

Time and Space Complexity

The provided code aims to correct a binary search tree (BST) where exactly two nodes have been swapped by mistake. To identify and swap them back, an in-order depth-first search (DFS) is employed.

Time Complexity

The time complexity of the DFS in a BST is O(N), where N is the total number of nodes in the tree. This is because the algorithm must visit every node exactly once to compare the values and find the misplaced nodes.

Space Complexity

The space complexity of the algorithm is O(H), where H is the height of the tree. This space complexity arises from the maximum size of the call stack when the recursive DFS reaches the deepest level of the tree. For a balanced tree, the height H would be log(N), thus giving a best case of O(log(N)).

However, in the worst case scenario where the tree becomes skewed, resembling a linked list, the height H becomes N, thereby degrading the space complexity to O(H) which is O(N) in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know