---
link: https://leetcode.com/problems/recover-binary-search-tree/
tags: tree, bst, hard
---

# 99. Recover Binary Search Tree

## Question
Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

**Example 1:**

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

**Example 2:**

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

**Follow up:**

- A solution using O(*n*) space is pretty straight forward.
- Could you devise a constant space solution?

## Solution

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

class Solution(object):
    def recoverTree(self, root):
        self.unordered_nodes = []
        self.prev = None
        self.helper(root)
        
        _ = self.unordered_nodes[0].val
        self.unordered_nodes[0].val = self.unordered_nodes[1].val
        self.unordered_nodes[1].val = _
    
    def helper(self, curr):
        if curr is None:
            return 
        
        self.helper(curr.left)
        
        if self.prev and self.prev.val > curr.val:
            if not self.unordered_nodes:
                self.unordered_nodes = [self.prev, curr]
            else:
                self.unordered_nodes[-1] = curr
        self.prev = curr
        
        self.helper(curr.right)
    
    def recoverTree_nlogn(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        self.list = []
        self.inorderTraversal(root)  # Inorder traversal of a BST is a sorted list.
        
        sorted_list = sorted(self.list)
        unordered_nodes = []
        for idx in range(len(self.list)):
            if self.list[idx][0] != sorted_list[idx][0]:
                unordered_nodes.append(self.list[idx][1])
        
            if len(unordered_nodes) == 2:
                break
        
        _ = unordered_nodes[0].val
        unordered_nodes[0].val = unordered_nodes[1].val
        unordered_nodes[1].val = _
        
        
    def inorderTraversal_nlogn(self, node):
        if node is None:
            return
        
        self.inorderTraversal(node.left)
        self.list.append((node.val, node))
        self.inorderTraversal(node.right)
        

## Solution: Java