Jobs

Interviews

Discussions

Recover Binary Search Tree

Medium

Google

4 views

Topics:

TreesRecursion

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.

For example:

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.

Another Example:

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^31 <= Node.val <= 2^31 - 1

Can you devise a constant O(1) space solution?

Recover Binary Search Tree

Medium

Google

4 views

Topics:

TreesRecursion

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.

For example:

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.

Another Example:

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^31 <= Node.val <= 2^31 - 1

Can you devise a constant O(1) space solution?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values of the nodes in the BST be any data type, or are they restricted to integers?
Is it guaranteed that there are exactly two nodes swapped, or could there be fewer (e.g., none) or more?
If there are no swaps required (the tree is already a valid BST), should I return the original root, or is there a different expected output?
Can the BST be empty (root is null)? If so, what is the expected output?
If the two swapped nodes have the same value, how should I handle that case?

Brute Force Solution

Approach

The goal is to fix a Binary Search Tree where two nodes are swapped accidentally. The brute force approach tries every possible pair of nodes in the tree, swaps them, and then checks if the resulting tree is a valid Binary Search Tree.

Here's how the algorithm would work step-by-step:

Consider every possible pair of nodes within the tree. This means taking each node and pairing it up with every other node in the tree.
For each pair of nodes, temporarily swap their values. Think of physically exchanging the labels on those two nodes.
After each swap, check if the entire tree now follows the rules of a Binary Search Tree. That is, for each node, all nodes in its left side have smaller values, and all nodes on its right side have larger values.
If, after a swap, the tree is a valid Binary Search Tree, then you have found the pair of nodes that were originally swapped. Stop, and undo the swap to restore the correct tree.
If you have gone through all possible pairs of nodes without finding a valid Binary Search Tree, then there may be an error in the tree or in how we are thinking about the solution.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def recover_binary_search_tree_brute_force(root):
    nodes = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            nodes.append(node)
            inorder_traversal(node.right)

    inorder_traversal(root)

    for first_node_index in range(len(nodes)):
        for second_node_index in range(first_node_index + 1, len(nodes)):
            first_node = nodes[first_node_index]
            second_node = nodes[second_node_index]

            # Temporarily swap the values of the two nodes
            first_node.value, second_node.value = second_node.value, first_node.value

            # After swapping, check if the tree is a valid BST
            if is_valid_bst(root):

                # If valid, swap back and return
                first_node.value, second_node.value = second_node.value, first_node.value
                return

            # If not valid, swap back to continue the search
            first_node.value, second_node.value = second_node.value, first_node.value

def is_valid_bst(root):
    def validate(node, low=-float('inf'), high=float('inf')):
        if not node:
            return True

        # Check if node's value is within the valid range
        if node.value <= low or node.value >= high:
            return False

        # Recursively validate left and right subtrees with updated ranges
        return validate(node.left, low, node.value) and validate(node.right, node.value, high)

    return validate(root)

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach iterates through all possible pairs of nodes in the tree. Finding all possible pairs of n nodes requires O(n^2) operations. For each of these pairs, we swap the nodes' values and then validate if the entire tree is a valid Binary Search Tree. Validating the BST requires traversing the entire tree, which takes O(n) time. Therefore, the overall time complexity is O(n^2) * O(n), which equals O(n^3).

Space Complexity

O(1) – The provided brute force approach involves swapping node values and checking for BST validity. It doesn't explicitly mention using any auxiliary data structures like lists, queues, or hash maps. The algorithm iterates through pairs of nodes, but this iteration happens in place without storing node references. Therefore, the space complexity is constant as it only uses a few variables for node traversal and swapping, independent of the number of nodes (N) in the BST.

Optimal Solution

Approach

The key to efficiently fixing a messed-up binary search tree lies in identifying the incorrectly placed nodes. We can do this by observing the order in which we should see the nodes if the tree were correct and noting any violations. The goal is to find these out-of-order nodes and swap them.

Here's how the algorithm would work step-by-step:

Imagine walking through the tree in a specific order: left, then current node, then right (this is called in-order traversal).
As you 'walk' through the tree, keep track of the last node you visited. If the current node's value is smaller than the last visited node's value, you've found a problem!
When you find the first violation, mark both the last visited node and the current node as potential candidates for the swap.
Keep walking through the tree. If you find another violation, you've likely found the second incorrectly placed node. Update your second candidate.
After you've walked through the entire tree, you'll have identified the two nodes that are out of place.
Now, simply swap the values of these two nodes. This will fix the binary search tree.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def recoverTree(self, root):
        self.first_incorrect_node = None
        self.second_incorrect_node = None
        self.previous_node = None

        def inorder_traversal(node):
            if not node:
                return

            inorder_traversal(node.left)

            # Check for violation of BST property
            if self.previous_node and node.val < self.previous_node.val:
                # This is the first violation, mark nodes.
                if not self.first_incorrect_node:
                    self.first_incorrect_node = self.previous_node
                    self.second_incorrect_node = node
                else:
                    # Found the second violation.
                    self.second_incorrect_node = node

            self.previous_node = node

            inorder_traversal(node.right)

        inorder_traversal(root)

        # Swap the values of the incorrect nodes.
        self.first_incorrect_node.val, self.second_incorrect_node.val = \
            self.second_incorrect_node.val, self.first_incorrect_node.val

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs an in-order traversal of the binary search tree. In-order traversal visits each node in the tree exactly once. Therefore, the time complexity is directly proportional to the number of nodes (n) in the tree, resulting in O(n) time complexity.

Space Complexity

O(H) – The in-order traversal, whether implemented iteratively using a stack or recursively, requires space to store the call stack (in the recursive case) or the stack data structure itself (in the iterative case). In the worst-case scenario (a skewed tree), the height H can be equal to N (number of nodes), leading to a stack size of O(N). However, for a balanced tree, the height is log N. Therefore, the auxiliary space complexity depends on the height of the tree, H, and not the number of nodes. The space needed for the variables tracking potential candidates for the swap (first, second, and previous nodes) is constant. Therefore, the overall auxiliary space complexity is O(H).

Edge Cases

Case	How to Handle
Null or empty tree	Return the null root immediately as there's nothing to correct.
Tree with only one node	Return the root as a single-node tree is inherently a valid BST.
Tree with only two nodes, swapped	Directly compare and swap the values of the two nodes if they are out of order.
Two adjacent nodes are swapped	The first and second violations in inorder traversal will directly point to the two swapped nodes.
Two non-adjacent nodes are swapped	The first violation will identify the first node, and the second violation will identify the second node.
Tree with duplicate values, including duplicates around the swapped nodes	The inorder traversal logic should still correctly identify the out-of-order nodes even with duplicates.
Tree with negative values	The comparison logic works correctly with negative numbers in inorder traversal.
Integer overflow if node values are very large (close to Integer.MAX_VALUE or Integer.MIN_VALUE)	Use long data type for comparison during inorder traversal to prevent potential overflows when calculating differences.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values of the nodes in the BST be any data type, or are they restricted to integers?
Is it guaranteed that there are exactly two nodes swapped, or could there be fewer (e.g., none) or more?
If there are no swaps required (the tree is already a valid BST), should I return the original root, or is there a different expected output?
Can the BST be empty (root is null)? If so, what is the expected output?
If the two swapped nodes have the same value, how should I handle that case?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible pair of nodes within the tree. This means taking each node and pairing it up with every other node in the tree.
For each pair of nodes, temporarily swap their values. Think of physically exchanging the labels on those two nodes.
After each swap, check if the entire tree now follows the rules of a Binary Search Tree. That is, for each node, all nodes in its left side have smaller values, and all nodes on its right side have larger values.
If, after a swap, the tree is a valid Binary Search Tree, then you have found the pair of nodes that were originally swapped. Stop, and undo the swap to restore the correct tree.
If you have gone through all possible pairs of nodes without finding a valid Binary Search Tree, then there may be an error in the tree or in how we are thinking about the solution.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def recover_binary_search_tree_brute_force(root):
    nodes = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            nodes.append(node)
            inorder_traversal(node.right)

    inorder_traversal(root)

    for first_node_index in range(len(nodes)):
        for second_node_index in range(first_node_index + 1, len(nodes)):
            first_node = nodes[first_node_index]
            second_node = nodes[second_node_index]

            # Temporarily swap the values of the two nodes
            first_node.value, second_node.value = second_node.value, first_node.value

            # After swapping, check if the tree is a valid BST
            if is_valid_bst(root):

                # If valid, swap back and return
                first_node.value, second_node.value = second_node.value, first_node.value
                return

            # If not valid, swap back to continue the search
            first_node.value, second_node.value = second_node.value, first_node.value

def is_valid_bst(root):
    def validate(node, low=-float('inf'), high=float('inf')):
        if not node:
            return True

        # Check if node's value is within the valid range
        if node.value <= low or node.value >= high:
            return False

        # Recursively validate left and right subtrees with updated ranges
        return validate(node.left, low, node.value) and validate(node.right, node.value, high)

    return validate(root)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine walking through the tree in a specific order: left, then current node, then right (this is called in-order traversal).
As you 'walk' through the tree, keep track of the last node you visited. If the current node's value is smaller than the last visited node's value, you've found a problem!
When you find the first violation, mark both the last visited node and the current node as potential candidates for the swap.
Keep walking through the tree. If you find another violation, you've likely found the second incorrectly placed node. Update your second candidate.
After you've walked through the entire tree, you'll have identified the two nodes that are out of place.
Now, simply swap the values of these two nodes. This will fix the binary search tree.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def recoverTree(self, root):
        self.first_incorrect_node = None
        self.second_incorrect_node = None
        self.previous_node = None

        def inorder_traversal(node):
            if not node:
                return

            inorder_traversal(node.left)

            # Check for violation of BST property
            if self.previous_node and node.val < self.previous_node.val:
                # This is the first violation, mark nodes.
                if not self.first_incorrect_node:
                    self.first_incorrect_node = self.previous_node
                    self.second_incorrect_node = node
                else:
                    # Found the second violation.
                    self.second_incorrect_node = node

            self.previous_node = node

            inorder_traversal(node.right)

        inorder_traversal(root)

        # Swap the values of the incorrect nodes.
        self.first_incorrect_node.val, self.second_incorrect_node.val = \
            self.second_incorrect_node.val, self.first_incorrect_node.val

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return the null root immediately as there's nothing to correct.
Tree with only one node	Return the root as a single-node tree is inherently a valid BST.
Tree with only two nodes, swapped	Directly compare and swap the values of the two nodes if they are out of order.
Two adjacent nodes are swapped	The first and second violations in inorder traversal will directly point to the two swapped nodes.
Two non-adjacent nodes are swapped	The first violation will identify the first node, and the second violation will identify the second node.
Tree with duplicate values, including duplicates around the swapped nodes	The inorder traversal logic should still correctly identify the out-of-order nodes even with duplicates.
Tree with negative values	The comparison logic works correctly with negative numbers in inorder traversal.
Integer overflow if node values are very large (close to Integer.MAX_VALUE or Integer.MIN_VALUE)	Use long data type for comparison during inorder traversal to prevent potential overflows when calculating differences.