Recover Binary Search Tree

class Solution {
public:
    void exchange(TreeNode* node1, TreeNode* node2) {
        int temp = node1->val;
        node1->val = node2->val;
        node2->val = temp;
    }
    void restoreTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *lastSeen = nullptr,
                 *morrisPredecessor = nullptr;
        while (root != nullptr) {
            if (root->left != nullptr) {
                morrisPredecessor = root->left;
                while (morrisPredecessor->right != nullptr &&
                       morrisPredecessor->right != root)
                    morrisPredecessor = morrisPredecessor->right;
                if (morrisPredecessor->right == nullptr) {
                    morrisPredecessor->right = root;
                    root = root->left;
                } else {
                    if (lastSeen != nullptr && root->val < lastSeen->val) {
                        second = root;
                        if (first == nullptr) first = lastSeen;
                    }
                    lastSeen = root;
                    morrisPredecessor->right = nullptr;
                    root = root->right;
                }
            } else {
                if (lastSeen != nullptr && root->val < lastSeen->val) {
                    second = root;
                    if (first == nullptr) first = lastSeen;
                }
                lastSeen = root;
                root = root->right;
            }
        }
        exchange(first, second);
    }
};

This solution repairs a binary search tree (BST) where two nodes have been swapped by mistake. The goal is to recover the tree without altering its structure.

The code defines a class Solution with two methods:

• exchange(TreeNode* node1, TreeNode* node2) swaps the values of two trees nodes.
• restoreTree(TreeNode* root) implements the logic to identify and fix the swapped nodes using an in-place algorithm without additional memory for recursion or a stack.

The code uses Morris traversal for in-order traversal of the BST:

• It initializes four pointers: first, second, lastSeen, and morrisPredecessor.
• The while loop runs as long as there are unvisited nodes (root is not nullptr).
• Inside the loop, the Morris traversal logic:
  • Builds a temporary threaded-binary-tree-like structure which enables in order traversal without recursion.
  • Keeps track of previous nodes (lastSeen) to find if the current node value is smaller.
  • Identifies two incorrect nodes during the traversal.
  • The tree structure is restored by breaking the temporary links (setting morrisPredecessor->right back to nullptr).

Once the traversal is completed and the two incorrect nodes are identified, the exchange(first, second) function is called to swap their values, thus correcting the tree structure.

This approach maintains the BST properties and fixes the swapped nodes efficiently using Morris Traversal, ensuring time complexity of O(n) and constant space complexity, O(1).

class Solution {
    public void exchange(TreeNode node1, TreeNode node2) {
        int temporary = node1.val;
        node1.val = node2.val;
        node2.val = temporary;
    }

    public void fixTree(TreeNode node) {
        TreeNode first = null, second = null, previous = null, morrisPred = null;

        while (node != null) {
            if (node.left != null) {
                morrisPred = node.left;
                while (morrisPred.right != null && morrisPred.right != node) {
                    morrisPred = morrisPred.right;
                }

                if (morrisPred.right == null) {
                    morrisPred.right = node;
                    node = node.left;
                } else {
                    if (previous != null && node.val < previous.val) {
                        second = node;
                        if (first == null) first = previous;
                    }
                    previous = node;

                    morrisPred.right = null;
                    node = node.right;
                }
            } else {
                if (previous != null && node.val < previous.val) {
                    second = node;
                    if (first == null) first = previous;
                }
                previous = node;

                node = node.right;
            }
        }
        exchange(first, second);
    }
}

This solution focuses on correcting a corrupted Binary Search Tree (BST) where two nodes are swapped. The algorithm efficiently utilizes the Morris Traversal method, ensuring a constant space complexity.

The Java implementation consists of two functions within the Solution class:

1. exchange(TreeNode node1, TreeNode node2)

   • Swaps the values of node1 and node2, facilitating the correction of the tree structure with a temporary variable holding one of the node values during the swap.

2. fixTree(TreeNode node)

   • Orchestrates the process of identifying and correcting the misplaced nodes:
     • Initialize pointers first, second, previous, and morrisPred to help in node comparisons and maintaining references.
     • Traverse the tree using Morris Traversal which optimizes space usage by eliminating the need for a separate stack or recursion:
       • If a node has a left child, navigate to the rightmost node of the left subtree (morrisPred) and establish temporary connections to retain tree structure.
       • If a misplaced node is detected (i.e., current node value is smaller than the previous node value), update the second pointer, and set the first pointer when needed.
       • Reset tree structure by resolving temporary connections.
     • Correct the BST by calling exchange on the identified first and second nodes after traversal is complete, restoring the tree’s order.

This method achieves optimal space usage while maintaining the tree's integrity, allowing for an in-place recovery of the BST. Implement this logic when a BST is corrupted by the swap of two nodes and a recovery without significant memory overhead is crucial.

typedef struct TreeNode TreeNode;
void swapNodes(TreeNode* node1, TreeNode* node2) {
    int temp = node1->val;
    node1->val = node2->val;
    node2->val = temp;
}
void restoreBST(TreeNode* root) {
    TreeNode* first = NULL;
    TreeNode* second = NULL;
    TreeNode* last = NULL;
    TreeNode* trail = NULL;
    while (root != NULL) {
        if (root->left != NULL) {
            trail = root->left;
            while (trail->right != NULL && trail->right != root) {
                trail = trail->right;
            }
            if (trail->right == NULL) {
                trail->right = root;
                root = root->left;
            } else {
                if (last != NULL && root->val < last->val) {
                    second = root;
                    if (first == NULL) first = last;
                }
                last = root;
                trail->right = NULL;
                root = root->right;
            }
        } else {
            if (last != NULL && root->val < last->val) {
                second = root;
                if (first == NULL) first = last;
            }
            last = root;
            root = root->right;
        }
    }
    swapNodes(first, second);
}

The C code provided outlines a method to correct a corrupted binary search tree (BST) where two nodes have been swapped by mistake. Here's an explanation of the objectives and processes employed in the solution:

• Objective: The goal is to restore the properties of the BST where every node's left child must have a value less than its own and every right child must have a value greater than its own.

• Structures and Functions:

  • TreeNode structure likely includes pointers to left and right child nodes, and an integer val to store the node's value.
  • swapNodes() function exchanges the values of two TreeNode objects, facilitating the correction of the BST structure.
  • restoreBST() is the core function responsible for identifying the two swapped nodes and restoring the correct order of the BST.

• Detailed Steps in restoreBST():

  1. Traverse the tree using a Morris In-order traversal to maintain constant space usage:
     • This traversal method uses a temporary link from the precursor (rightmost node of the left subtree) back to the current node, facilitating in-order traversal without additional stack or recursion.
  2. Identify the two nodes that are swapped:
     • During traversal, compare each node with the last visited node (last). The first time a node is encountered that has a smaller value than last, mark this node as the potential first swapped node.
     • Continue traversing, and when a similar condition is met again, update or confirm the swapped nodes (first and second).
  3. After traversal, use the swapNodes() function to swap back the values of the two identified erroneous nodes, thus restoring the BST properties.

By analyzing the structure, flow, and logic of your program, ensure the BST is correctly restored with the least time and space complexity involved in a Morris traversal method. This method proves efficient by using a threading technique which circumvents auxiliary data structures for tracking traversal paths.

var restoreBST = function (node) {
    var first = null,
        second = null,
        previous = null,
        ancestor = null;

    while (node !== null) {
        if (node.left !== null) {
            ancestor = node.left;
            
            while (ancestor.right !== null && ancestor.right !== node)
                ancestor = ancestor.right;

            if (ancestor.right === null) {
                ancestor.right = node;
                node = node.left;
            } else {
                if (previous !== null && node.val < previous.val) {
                    second = node;
                    if (first === null) first = previous;
                }
                previous = node;
                ancestor.right = null;
                node = node.right;
            }
        } else {
            if (previous !== null && node.val < previous.val) {
                second = node;
                if (first === null) first = previous;
            }
            previous = node;
            node = node.right;
        }
    }

    var temp = first.val;
    first.val = second.val;
    second.val = temp;
};

Recover an incorrectly swapped nodes in a Binary Search Tree (BST) using JavaScript. Here's how the given solution corrects the tree:

• Initialize four variables: first, second, previous, and ancestor to manage nodes during traversal.
• Use a while loop to navigate through the tree with the help of Morris In-order traversal, which conserves memory by avoiding recursion or a stack.
• Within the loop:
  • If the current node node has a left child, find the rightmost node of the left subtree, referred to here as ancestor.
  • Employ a conditional setup to either build a temporary threaded link from ancestor back to node (if not already present) or to identify and fix the disorder when revisiting node (thread exists).
  • Continuously update the previous node as the reference to the last node encountered in in-order traversal.
  • If no left child exists, directly compare node with previous to check for discrepancies in the expected in-order sequence.
• After the tree traversal, if any two nodes were identified (first and second) where values were out of the intended order, swap their values.
• This restoration process ensures the BST's properties remain intact without additional space for traversal mechanics.

This approach is efficient in node handling and operates in linear time, making it a favorable option for large trees where maintaining a balanced or correct order is critical for subsequent operations.

class Solution:
    def restoreBST(self, rootNode: TreeNode) -> None:
        current = previous = first = second = last = None

        while rootNode:
            if rootNode.left:
                # Finding the predecessor node
                current = rootNode.left
                while current.right and current.right != rootNode:
                    current = current.right

                # Making a temporary link or breaking it
                if current.right is None:
                    current.right = rootNode
                    rootNode = rootNode.left
                else:
                    if previous and rootNode.val < previous.val:
                        second = rootNode
                        if first is None:
                            first = previous
                    previous = rootNode

                    current.right = None
                    rootNode = rootNode.right
            else:
                if previous and rootNode.val < previous.val:
                    second = rootNode
                    if first is None:
                        first = previous
                previous = rootNode

                rootNode = rootNode.right

        first.val, second.val = second.val, first.val

The Python code provided defines a method to recover a corrupted Binary Search Tree (BST) where two nodes are swapped by mistake. It uses Morris Traversal for this purpose, which is a way to traverse the tree without using additional space for recursion or a stack.

Here's a concise walkthrough of the approach used:

• Initialization: Variables current, previous, first, second, and last are initialized to None. These help keep track of the traversal and the nodes that need to be swapped.

• Traversing the Tree:

  • The outer while loop helps navigate through the tree starting from the rootNode.
  • If a node has a left child, the algorithm finds its predecessor (the rightmost node in the left subtree).
  • If the predecessor's right pointer is None, it points it temporarily to the current node (rootNode). This is part of setting up Morris Traversal to revert these changes later.
  • If the link between the predecessor and the current node already exists, it is a sign to break this temporary link and to check if the previous node value is greater than the current node value, indicating a potential misplaced node.

• Identifying Misplaced Nodes:

  • While traversing, if the value of the previous node is greater than the rootNode (current node), it identifies a violation of BST properties.
  • The first occurrence of such a violation captures the previous node as first and the current node as second.
  • If more violations are found, second is updated to the current node.

• Swapping Values:

  • After the traversal completes, the values of first and second are swapped. This corrects the BST by putting the nodes in their correct positions.

The method modifies the BST in-place and efficiently resolves the issue without using extra space for data structures like arrays or additional trees, making Morris Traversal a space-efficient technique for tree operations.