99. Recover Binary Search 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
tofirst
. - 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
, andsecond
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. Thefirst
anomaly is when we set theprev
as thefirst
, and the next anomaly detected involves settingsecond
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 expressionfirst.val, second.val = second.val, first.val
.
Here is what the code does, broken down by each line:
prev = first = second = None
: Initialize variables toNone
.prev
will track the most recent node during in-order traversal, whilefirst
andsecond
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 isNone
, 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 ofprev
, which would indicate a violation of the BST properties.if first is None: first = prev
: Iffirst
is not set, it means this is the first anomaly found, and we setfirst
toprev
.second = root
: Whether the current anomaly is the first or subsequent, updatesecond
to the current node (root
).prev = root
: Updateprev
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 EvaluatorExample 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
, andsecond
asNone
. -
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, encountering5
. This is where we first notice the order is incorrect since5
>2
, butprev
isNone
, so we move on. -
Next, we traverse to
4
. Here we findprev.val
(which is5
) >root.val
(which is4
). This is our first anomaly, so we setfirst
toprev
(5
) and leavesecond
asNone
for now. -
We continue our traversal. Now
prev
is set to4
. When we get to3
, we see thatprev.val
(4
) >root.val
(3
). We've found our second anomaly. We assignsecond
to the current node (3
). -
We finish the traversal by visiting the remaining nodes (
6
and7
), 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.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Want a Structured Path to Master System Design Too? Donāt Miss This!