grid47 Exploring patterns and algorithms
Oct 28, 2024
5 min read
Solution to LeetCode 99: Recover Binary Search Tree Problem
You are given the root of a binary search tree (BST), but two nodes in the tree were swapped by mistake. Your task is to recover the tree by swapping the two nodes back, without changing the structure of the tree.
Problem
Approach
Steps
Complexity
Input: The input consists of the root node of a binary search tree.
Example: Input: root = [2, 4, 3, 1]
Constraints:
• The tree contains between 2 and 1000 nodes.
• -2^31 <= Node.val <= 2^31 - 1
Output: Return the root of the binary search tree after recovering the swapped nodes.
Example: Output: [3, 4, 2, 1]
Constraints:
• The function should return the corrected BST.
Goal: The goal is to identify the two swapped nodes and swap them back to restore the BST's validity.
Steps:
• Perform an inorder traversal of the tree while keeping track of the previously visited node.
• Identify the two nodes that are out of order during the traversal.
• Once both swapped nodes are found, swap their values to restore the tree.
Goal: The input tree contains between 2 and 1000 nodes, and node values are within the 32-bit signed integer range.
Steps:
• The number of nodes in the tree is between 2 and 1000.
• Node values are within the range of [-2^31, 2^31 - 1].
Assumptions:
• The binary tree is a valid BST, except for the two swapped nodes.
• Input: Input: root = [2, 4, 3, 1]
• Explanation: In this case, nodes 2 and 4 were swapped, so swapping them back will restore the binary search tree to [3, 4, 2, 1].
• Input: Input: root = [3, 1, 4, null, null, 2]
• Explanation: Here, nodes 2 and 3 were swapped. Swapping them back restores the binary search tree to [2, 1, 4, null, null, 3].
Approach: To recover the tree, we will perform an inorder traversal of the tree to identify the two nodes that are out of order and swap them back to their correct positions.
Observations:
• During an inorder traversal of a valid BST, the nodes should appear in increasing order.
• We need to identify the two nodes that are swapped and restore their positions by swapping their values.
Steps:
• Traverse the tree using an inorder traversal.
• Identify the first and second nodes where the order is violated (i.e., current node value < previous node value).
• Swap the values of these two nodes to restore the binary search tree.
Empty Inputs:
• There are no empty inputs in this problem as the tree always contains at least 2 nodes.
Large Inputs:
• The solution should be efficient enough to handle trees with up to 1000 nodes.
Special Values:
• Ensure that node values are handled correctly even for extreme values such as -2^31 and 2^31 - 1.
Constraints:
• The tree must contain at least 2 nodes, and values must lie within the specified range.
Here we declare three pointers: 'prv' (previous node), 'fst' (first wrong node), and 'scd' (second wrong node) to track the swapped nodes.
2 : Function Definition
void inorder(TreeNode* node)
We define the inorder function that will traverse the tree and detect swapped nodes.
3 : Base Case
if(!node) return;
This is the base case. If the current node is null, we return from the function.
4 : Left Subtree Traversal
inorder(node->left);
We recursively call the inorder function on the left child of the current node to traverse the left subtree.
5 : BST Violation Check
if (prv && node->val < prv->val) {
We check if the current node's value is less than the previous node's value, indicating a violation of BST properties.
6 : Identify First Swapped Node
if (!fst) fst = prv;
If we haven't found the first swapped node yet, we set 'fst' to the previous node.
7 : Identify Second Swapped Node
scd = node;
We set 'scd' to the current node as it is the second wrong node.
8 : Update Previous Node
prv = node;
We update the 'prv' pointer to the current node for future comparisons.
9 : Right Subtree Traversal
inorder(node->right);
We recursively call the inorder function on the right child of the current node to continue the traversal.
10 : Tree Recovery Function
voidrecoverTree(TreeNode* node) {
We define the public method 'recoverTree' that will initiate the inorder traversal to detect swapped nodes.
11 : Recover Swapped Nodes
inorder(node);
We call the inorder function to detect and set 'fst' and 'scd' as the swapped nodes.
12 : Swap Nodes
swap(fst->val, scd->val);
We swap the values of the two detected swapped nodes to restore the BST.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of nodes in the tree, because we need to traverse all nodes to identify the swapped nodes.
Best Case: O(1)
Worst Case: O(n)
Description: In the worst case, the space complexity is O(n) due to the recursion stack. However, for an iterative approach, the space complexity can be reduced to O(1).
