HomeLeetcode99. Recover Binary Search Tree - Leetcode Solutions
Leetcode

99. Recover Binary Search Tree – Leetcode Solutions

Declan Clarke

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.

Examples:

Example 1:
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.

Example 2:
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.

Solution in Python:

To recover a binary search tree (BST) where exactly two nodes have been swapped by mistake, we need to identify these two nodes and swap their values back to correct the BST. We can achieve this using an in-order traversal of the tree, which should yield a sorted sequence if the tree is a valid BST.

For the problem constraints, we aim to solve it with O(1) space complexity (excluding the recursion stack). This can be done using Morris Traversal, which allows in-order traversal without extra space.

Python
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # Initialize pointers needed for Morris Traversal
        first_element = second_element = None
        prev_element = TreeNode(float('-inf'))
        
        # Helper function to swap values of two nodes
        def swap(x, y):
            x.val, y.val = y.val, x.val
        
        # Morris Traversal to find the two nodes
        current = root
        while current is not None:
            if current.left is None:
                # Visit the node
                if prev_element.val > current.val:
                    if first_element is None:
                        first_element = prev_element
                    second_element = current
                
                prev_element = current
                current = current.right
            else:
                # Find the rightmost node in the left subtree or the predecessor
                predecessor = current.left
                while predecessor.right is not None and predecessor.right is not current:
                    predecessor = predecessor.right
                
                # Make current as the right child of its predecessor
                if predecessor.right is None:
                    predecessor.right = current
                    current = current.left
                else:
                    # Revert the changes made
                    predecessor.right = None
                    if prev_element.val > current.val:
                        if first_element is None:
                            first_element = prev_element
                        second_element = current
                    
                    prev_element = current
                    current = current.right
        
        # Swap the values of the two nodes to correct the tree
        swap(first_element, second_element)

Explanation of the Code

  1. Initialization:
    • first_element and second_element are pointers to the two nodes that need to be swapped.
    • prev_element is initialized to a very small value to keep track of the previous node during the in-order traversal.
  2. Morris Traversal:
    • current starts at the root of the tree.
    • If current has no left child, it is visited directly.
    • If current has a left child, find its predecessor (the rightmost node in the left subtree).
    • If the predecessor’s right child is None, make current the right child of the predecessor and move current to its left child.
    • If the predecessor’s right child is current, revert the changes (i.e., remove the temporary link) and visit current.
  3. Finding the Two Nodes:
    • During the in-order traversal, if prev_element.val > current.val, it means there is a violation of the BST property.
    • The first such violation identifies the first_element and possibly the second_element.
    • Any subsequent violation will identify the second_element.
  4. Swapping the Nodes:
    • After identifying the two misplaced nodes, swap their values to correct the BST.

This approach ensures that we achieve the desired O(1) space complexity by using Morris Traversal, and it correctly recovers the tree structure by identifying and swapping the two misplaced nodes.

Solution in Javascript:

JavaScript
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    // Initialize pointers needed for Morris Traversal
    let firstElement = null;
    let secondElement = null;
    let prevElement = new TreeNode(Number.NEGATIVE_INFINITY);
    
    // Helper function to swap values of two nodes
    const swap = (x, y) => {
        let temp = x.val;
        x.val = y.val;
        y.val = temp;
    };
    
    // Morris Traversal to find the two nodes
    let current = root;
    while (current !== null) {
        if (current.left === null) {
            // Visit the node
            if (prevElement.val > current.val) {
                if (firstElement === null) {
                    firstElement = prevElement;
                }
                secondElement = current;
            }
            prevElement = current;
            current = current.right;
        } else {
            // Find the rightmost node in the left subtree or the predecessor
            let predecessor = current.left;
            while (predecessor.right !== null && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            
            // Make current as the right child of its predecessor
            if (predecessor.right === null) {
                predecessor.right = current;
                current = current.left;
            } else {
                // Revert the changes made
                predecessor.right = null;
                if (prevElement.val > current.val) {
                    if (firstElement === null) {
                        firstElement = prevElement;
                    }
                    secondElement = current;
                }
                prevElement = current;
                current = current.right;
            }
        }
    }
    
    // Swap the values of the two nodes to correct the tree
    swap(firstElement, secondElement);
};

Solution in Java:

Java
class Solution {
    private TreeNode firstElement = null;
    private TreeNode secondElement = null;
    private TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {
        // Morris Traversal to find the two nodes
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                // Visit the node
                if (prevElement.val > current.val) {
                    if (firstElement == null) {
                        firstElement = prevElement;
                    }
                    secondElement = current;
                }
                prevElement = current;
                current = current.right;
            } else {
                // Find the rightmost node in the left subtree or the predecessor
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                // Make current as the right child of its predecessor
                if (predecessor.right == null) {
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Revert the changes made
                    predecessor.right = null;
                    if (prevElement.val > current.val) {
                        if (firstElement == null) {
                            firstElement = prevElement;
                        }
                        secondElement = current;
                    }
                    prevElement = current;
                    current = current.right;
                }
            }
        }

        // Swap the values of the two nodes to correct the tree
        swap(firstElement, secondElement);
    }

    private void swap(TreeNode x, TreeNode y) {
        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
}

Solution in C#:

C#
public class Solution {
    private TreeNode firstElement = null;
    private TreeNode secondElement = null;
    private TreeNode prevElement = new TreeNode(int.MinValue);

    public void RecoverTree(TreeNode root) {
        // Morris Traversal to find the two nodes
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                // Visit the node
                if (prevElement.val > current.val) {
                    if (firstElement == null) {
                        firstElement = prevElement;
                    }
                    secondElement = current;
                }
                prevElement = current;
                current = current.right;
            } else {
                // Find the rightmost node in the left subtree or the predecessor
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                // Make current as the right child of its predecessor
                if (predecessor.right == null) {
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Revert the changes made
                    predecessor.right = null;
                    if (prevElement.val > current.val) {
                        if (firstElement == null) {
                            firstElement = prevElement;
                        }
                        secondElement = current;
                    }
                    prevElement = current;
                    current = current.right;
                }
            }
        }

        // Swap the values of the two nodes to correct the tree
        Swap(firstElement, secondElement);
    }

    private void Swap(TreeNode x, TreeNode y) {
        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com