Recover Binary Search Tree

                                            
/*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x): val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *prev = NULL, *first = NULL, *second = NULL;
        inorder(root, prev, first, second);
        swap(first->val, second->val);
    }
    
    void inorder(TreeNode* root, TreeNode*& prev, TreeNode*& first, TreeNode*& second) {
        if(root == NULL) return;
        
        inorder(root->left, prev, first, second);
        
        if(prev != NULL && prev->val > root->val) {
            if(first == NULL) first = prev;
            second = root;
        }
        
        prev = root;
        
        inorder(root->right, prev, first, second);
    }
};

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):

class Solution(object):
    def recoverTree(self, root):
        first = None
        second = None
        prev = TreeNode(float('-inf'))
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if first is None and prev.val >= root.val:
                first = prev
            if first is not None and prev.val >= root.val:
                second = root
            prev = root
            root = root.right
        first.val, second.val = second.val, first.val

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void recoverTree(struct TreeNode* root){
    struct TreeNode *first = NULL, *second = NULL, *prev = NULL, *temp = NULL;
    struct TreeNode* current = root;
    
    while(current != NULL){
        if(current->left == NULL){
            if(prev != NULL && prev->val > current->val){
                if(first == NULL){
                    first = prev;
                    second = current;
                }
                else{
                    second = current;
                }
            }
            prev = current;
            current = current->right;
        }
        else{
            temp = current->left;
            while(temp->right != NULL && temp->right != current){
                temp = temp->right;
            }
            
            if(temp->right == NULL){
                temp->right = current;
                current = current->left;
            }
            else{
                temp->right = NULL;
                if(prev->val > current->val){
                    if(first == NULL){
                        first = prev;
                        second = current;
                    }
                    else{
                        second = current;
                    }
                }
                prev = current;
                current = current->right;
            }
        }
    }
    
    int tempVal = first->val;
    first->val = second->val;
    second->val = tempVal;
}

                                            
public class Solution {
    public void RecoverTree(TreeNode root) {
        TreeNode x = null, y = null, pred = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (stack.Count > 0 || root != null) {
            while (root != null) {
                stack.Push(root);
                root = root.left;
            }
            
            root = stack.Pop();
            
            if (pred != null && root.val < pred.val) {
                y = root;
                if (x == null) {
                    x = pred;
                } else {
                    break;
                }
            }
            pred = root;
            root = root.right;
        }
        
        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 */

var recoverTree = function(root) {
    let first = null;
    let second = null;
    let prev = new TreeNode(-Infinity);
    
    const inorder = (node) => {
        if (node === null) return;
        
        inorder(node.left);
        
        if (first === null && prev.val >= node.val) {
            first = prev;
        }
        
        if (first !== null && prev.val >= node.val) {
            second = node;
        }
        
        prev = node;
        
        inorder(node.right);
    };
    
    inorder(root);
    
    let temp = first.val;
    first.val = second.val;
    second.val = temp;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function recoverTree(root: TreeNode | null): void {
    let prev = null;
    let first: TreeNode | null = null;
    let second: TreeNode | null = null;
    
    function inorder(node: TreeNode | null): void {
        if (!node) return;
        
        inorder(node.left);
        
        if (prev && prev.val >= node.val) {
            if (!first) {
                first = prev;
            }
            second = node;
        }
        
        prev = node;
        
        inorder(node.right);
    }
    
    inorder(root);
    
    if (first && second) {
        const temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return NULL
     */
    function recoverTree($root) {
        $first = null;
        $second = null;
        $prev = new TreeNode(-INF);
        
        $this->inOrderTraversal($root, $prev, $first, $second);
        
        // Swap the values of the two nodes
        $temp = $first->val;
        $first->val = $second->val;
        $second->val = $temp;
    }
    
    function inOrderTraversal($root, &$prev, &$first, &$second) {
        if ($root == null) return;
        
        $this->inOrderTraversal($root->left, $prev, $first, $second);
        
        if ($first == null && $prev->val >= $root->val) {
            $first = $prev;
        }
        
        if ($first != null && $prev->val >= $root->val) {
            $second = $root;
        }
        
        $prev = $root;
        
        $this->inOrderTraversal($root->right, $prev, $first, $second);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func recoverTree(_ root: TreeNode?) {
        var prev: TreeNode? = nil
        var first: TreeNode? = nil
        var second: TreeNode? = nil
        traverse(root, &prev, &first, &second)
        if let firstNode = first, let secondNode = second {
            let temp = firstNode.val
            firstNode.val = secondNode.val
            secondNode.val = temp
        }
    }
    
    func traverse(_ node: TreeNode?, _ prev: inout TreeNode?, _ first: inout TreeNode?, _ second: inout TreeNode?) {
        if node == nil { return }
        
        traverse(node!.left, &prev, &first, &second)
        
        if let previous = prev {
            if previous.val > node!.val {
                if first == nil {
                    first = previous
                }
                second = node
            }
        }
        prev = node
        
        traverse(node!.right, &prev, &first, &second)
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func recoverTree(root *TreeNode) {
    var first, second, pre *TreeNode
    var traverse func(node *TreeNode)
    
    traverse = func(node *TreeNode) {
        if node == nil {
            return
        }
        
        traverse(node.Left)
        
        if pre != nil && pre.Val > node.Val {
            if first == nil {
                first = pre
            }
            second = node
        }
        
        pre = node
        
        traverse(node.Right)
    }
    
    traverse(root)
    
    first.Val, second.Val = second.Val, first.Val
}

To solve this coding challenge, we need to recover a Binary Search Tree (BST) in which exactly two nodes have been swapped by mistake, without altering the structure of the tree. The constraints require us to achieve this recovery in an efficient manner, with the follow-up hint suggesting an O(1) space solution.

Explanation

The key properties of a BST we need to rely on are:

The left subtree of a node contains only nodes with values less than the node's value.
The right subtree of a node contains only nodes with values greater than the node's value.
An in-order traversal (left-root-right) of the BST should produce a sorted sequence of values.

Given this, our approach will be based on identifying the two nodes that have been swapped by looking for the anomalies in the in-order traversal of the tree. Specifically, we expect to see exactly two out-of-order pairs of consecutive nodes in the in-order traversal. By swapping the values of these two nodes, we can restore the BST.

We'll discuss the methodology step-by-step:

Step-by-Step Explanation

In-Order Traversal : Perform an in-order traversal of the BST to generate a sequence of node values.
Identify Anomalies : Identify the two nodes where the BST property is violated.
Swap Values : Swap the values of these two nodes to correct the BST.

Detailed Steps in Pseudocode

Utility Definitions :

Define the data structure for the tree nodes.
Define placeholder variables to hold the swapped nodes.

In-Order Traversal :

Traverse the tree using in-order traversal while tracking the previous node.
Identify the two out-of-order nodes during traversal.
Use a stack to implement the iterative in-order traversal approach.

Node Value Swap :

Once the two nodes are identified, swap their values.

Detailed Pseudocode with Comments

                                            
# Definition for a binary tree node
class TreeNode:
    # Initialization of TreeNode
    function __init__(value=0, left=None, right=None):
        this.value = value
        this.left = left
        this.right = right

# Function to recover the BST
function recoverTree(root):
    # Initialization of variables to track the swapped nodes
    firstSwappedNode = None
    secondSwappedNode = None
    previousNode = TreeNode(value=float('-inf'))  # Negative infinity as initial previous node
    stack = []  # Stack for iterative traversal

    # Perform in-order traversal
    while not stack.isEmpty() or root is not None:
        # Traverse to the leftmost node
        while root is not None:
            stack.append(root)
            root = root.left
        
        # Process the node
        root = stack.pop()
        
        # Identify out-of-order nodes
        if firstSwappedNode is None and previousNode.value >= root.value:
            firstSwappedNode = previousNode
        if firstSwappedNode is not None and previousNode.value >= root.value:
            secondSwappedNode = root
        
        # Update previous node and move to right subtree
        previousNode = root
        root = root.right
    
    # Swap values of the first and second swapped nodes
    if firstSwappedNode is not None and secondSwappedNode is not None:
        tempValue = firstSwappedNode.value
        firstSwappedNode.value = secondSwappedNode.value
        secondSwappedNode.value = tempValue

In this pseudocode, the emphasis is placed on utilizing an iterative in-order traversal with a stack to avoid recursive calls and maintain O(1) space complexity for the actual functional computations. The pseudo-comments inline explain the purpose of each block, and the variable names are chosen descriptively to reflect their purpose for clarity. This solution ensures that the structure of the BST remains unchanged while correcting the values of the swapped nodes, making the tree valid according to BST properties.