We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Recover Binary Search Tree

Difficulty: Medium

Problem 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.

Key Insights

  • A Binary Search Tree (BST) maintains the property that for every node, values in its left subtree are less, and values in its right subtree are greater.
  • When two nodes are swapped, there will be exactly two violations of the BST properties.
  • In-order traversal of a BST yields a sorted array, so during this traversal, we can identify the swapped nodes by tracking the previous node's value.
  • We need to restore the original values of the swapped nodes to recover the BST.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (for the constant space solution)

Solution

To recover the BST, we can perform an in-order traversal of the tree while keeping track of the previous node. During the traversal, if we find that the current node's value is less than the previous node's value, we have identified a violation. We will track the first and second nodes that are found to be swapped. After identifying both nodes, we simply swap their values to recover the BST.

  1. Perform an in-order traversal of the BST.
  2. During the traversal, maintain references to the previous node and identify the two nodes that are swapped.
  3. Swap the values of the identified nodes to restore the BST.

Code Solutions

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: TreeNode) -> None:
        # Initialize variables to keep track of the swapped nodes
        first = second = prev = None
        
        def inorder(node):
            nonlocal first, second, prev
            if not node:
                return
            
            inorder(node.left)  # Traverse left subtree
            
            # If the current node's value is less than the previous node's value
            if prev and node.val < prev.val:
                # If it's the first violation, mark these nodes
                if not first:
                    first = prev
                # Mark the second node
                second = node
            
            prev = node  # Update previous node
            
            inorder(node.right)  # Traverse right subtree
        
        inorder(root)  # Perform in-order traversal
        
        # Swap the values of the two nodes
        if first and second:
            first.val, second.val = second.val, first.val
← Back to All Questions