99. Recover Binary Search Tree

Problem

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?

Problem Summary

Two nodes in a binary search tree are mistakenly swapped. Recover the tree without changing its structure.

Solution Thought Process

• In a binary search tree, the values of 2 nodes are incorrect, and we need to fix these two nodes.
• For this problem, the two problematic nodes can be found with one preorder traversal, because the root node is visited first, then the left child, then the right child. When using preorder traversal on a binary search tree, the root node is greater than all nodes in the left subtree, and the root node is smaller than all nodes in the right subtree. So if the left subtree is greater than the root node, disorder has occurred; if the root node is greater than the right subtree, disorder has occurred. During traversal, if in the left subtree the value of the previously traversed node is greater than the value of the current root node, then an erroneous node has appeared; record it. Continue traversing until the second such node is found. Finally, when swapping these two nodes, only swap their values, rather than swapping the corresponding pointer references of these two nodes.

Code

package leetcode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverTree(root *TreeNode) {
	var prev, target1, target2 *TreeNode
	_, target1, target2 = inOrderTraverse(root, prev, target1, target2)
	if target1 != nil && target2 != nil {
		target1.Val, target2.Val = target2.Val, target1.Val
	}

}

func inOrderTraverse(root, prev, target1, target2 *TreeNode) (*TreeNode, *TreeNode, *TreeNode) {
	if root == nil {
		return prev, target1, target2
	}
	prev, target1, target2 = inOrderTraverse(root.Left, prev, target1, target2)
	if prev != nil && prev.Val > root.Val {
		if target1 == nil {
			target1 = prev
		}
		target2 = root
	}
	prev = root
	prev, target1, target2 = inOrderTraverse(root.Right, prev, target1, target2)
	return prev, target1, target2
}