BSTRECOVER - Editorial

editorial
1

Prerequisites :- Binary Search Trees, BT traversals.

Problem :- Given a binary search tree, where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Solution Approach :- The approach involves performing an inorder traversal of the BST to detect the misplaced nodes. The key insight is that in an inorder traversal of a BST, the values should be in ascending order. If there are misplaced nodes, there will be points where the current node’s value is smaller than the previous node’s value. The goal is to identify the first and second misplaced nodes and then swap their values.

Algorithm:

    1. Initialize three pointers: first_node, second_node, and prev_node.
    1. Implement an inorderTraversal function to traverse the BST in inorder.
    1. In the traversal:
    • If first_node is not assigned and the current node’s value is smaller than the previous node’s value, set first_node to the prev_node.
    • If first_node is assigned and the current node’s value is smaller than the previous node’s value, set second_node to the current node.
    • Update prev_node to the current node.
    1. After the traversal, swap the values of first_node and second_node.
    1. Return the modified root.

Time Complexity: O(N), because in the worst case, the algorithm visits all the nodes in the given BST.

Space complexity: O(1), because constant space (for few variables) is used.