#99 Leetcode Recover Binary Search Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode

#1 Code Example with C Programming

Code - C Programming

void find_nodes(struct TreeNode *node,
                struct TreeNode **n1,
                struct TreeNode **n2,
                struct TreeNode **n3,
                struct TreeNode **p) {
    if (!node || *n3) return;            // all are found
    
    find_nodes(node->left, n1, n2, n3, p);
    
    if (*p && (*p)->val > node->val) {  // found two nodes in wrong order
        if (!*n1) {
            *n1 = *p;                   // save first node
            *n2 = node;                 // save second node
        } else {
            *n3 = node;                 // save third node
            return;                     // all are found
        }
    }
    *p = node;
    
    find_nodes(node->right, n1, n2, n3, p);
}
void recoverTree(struct TreeNode* root) {
    struct TreeNode *n1, *n2, *n3, *p;
    int k;
    
    n1 = n2 = n3 = p = NULL;
    
    find_nodes(root, &n1, &n2, &n3, &p);
    
    if (n1) {
        if (!n3) n3 = n2;
        k = n1->val;            // swap first and third node
        n1->val = n3->val;
        n3->val = k;
    }
}

Input

Output

#2 Code Example with C++ Programming

Code - C++ Programming

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* pre = NULL, *one = NULL, *two = NULL;
        DFS(root, pre, one, two);
        swap(one->val, two->val);
    }
    
    void DFS(TreeNode* cur, TreeNode* &pre, TreeNode* &one, TreeNode* &two){
        if(!cur) return;
        DFS(cur->left, pre, one, two);
        if(pre && cur->val  <  pre->val){
            if(!one) one = pre;
            two = cur;
        }
        pre = cur;
        DFS(cur->right, pre, one, two);
    }
};

Input

Output

#3 Code Example with Java Programming

Code - Java Programming

class Solution {
  public void recoverTree(TreeNode root) {
    TreeNode nodeOne = null;
    TreeNode nodeTwo = null;
    TreeNode prevNode = null;
    Stack < TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      if (!stack.isEmpty()) {
        root = stack.pop();
        if (nodeOne == null && prevNode != null && prevNode.val > root.val) {
          nodeOne = prevNode;
        }
        if (nodeOne != null && prevNode.val > root.val) {
          nodeTwo = root;
        }
        prevNode = root;
        root = root.right;
      }
    }
    int tempValue = nodeOne.val;
    nodeOne.val = nodeTwo.val;
    nodeTwo.val = tempValue;
  }
}

Input

#4 Code Example with Javascript Programming

Code - Javascript Programming

const recoverTree = function(root) {
  let node1, node2;
  let prev = new TreeNode(-Infinity);
  traverse(root);
  swap(node1, node2)
    
  function traverse(node) {
    if (!node) return;
    traverse(node.left);
    if (node.val  <  prev.val) {
      node2 = node;
      if (!node1) node1 = prev;
    }
    prev = node;
    traverse(node.right);
  }

  function swap(node1, node2) {
    let temp = node1.val
    node1.val = node2.val
    node2.val = temp
  }
}

Input

Output

#5 Code Example with Python Programming

Code - Python Programming

class Solution:
    def recoverTree(self, root):
        def inorder(node):
            if node.left:
                yield from inorder(node.left)
            yield node
            if node.right:
                yield from inorder(node.right)
        swap1 = swap2 = smaller = None
        for node in inorder(root):   
            if smaller and smaller.val > node.val:
                if not swap1:  
                    swap1 = smaller
                swap2 = node      
            smaller = node
        if swap1:
            swap1.val, swap2.val = swap2.val, swap1.val

Input

Output

#6 Code Example with C# Programming

Code - C# Programming

using System.Collections.Generic;

namespace LeetCode
{
    public class _099_RecoverBinarySearchTree
    {
        private Stack < TreeNode> stack = new Stack();
        private TreeNode prev = null;
        private TreeNode first = null;
        private TreeNode second = null;
        private TreeNode current = null;

        public void RecoverTree(TreeNode root)
        {
            current = root;
            while (stack.Count > 0 || current != null)
            {
                while (current != null)
                {
                    stack.Push(current);
                    current = current.left;
                }

                current = stack.Pop();
                if (prev != null && current.val  <  prev.val)
                {
                    if (first == null) first = prev;
                    second = current;
                }
                if (first != null && first.val  <  current.val) break;

                prev = current;
                current = current.right;
            }

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

Input

Output