Leetcode OJ: Recover Binary Search Tree

Recover Binary Search Tree

 

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure. 

An O(n) space algorithm is straight-forward. One can write the in-order traversal of the BST to a linear array, then find the two swapped elements and swap them back.

A better solution is to not explicitly write the in-order traversal to an array. In fact, we can just do an in-order traversal on the BST itself and find the swapped elements in the process. Notice that if we exchange two adjacent (in terms of in-order) nodes, then the logic to find swapped elements is a little different, but this is handled subtly in the code.

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	TreeNode first = null;
	TreeNode second = null;
	TreeNode afterFirst = null;
	public void recoverTree(TreeNode root) {
	inOrder(root, null);
	if (second == null) {
	second = afterFirst;
	}
	int temp = first.val;
	first.val = second.val;
	second.val = temp;
	}
	public TreeNode inOrder(TreeNode root, TreeNode prev) {
	if (root == null) {
	return prev;
	}
	prev = inOrder(root.left, prev);
	if (prev != null && prev.val > root.val) {
	if (first == null) {
	first = prev;
	afterFirst = root;
	} else {
	second = root;
	}
	}
	return inOrder(root.right, root);
	}
	}

view raw recursive solution hosted with ❤ by GitHub

However, since the previous solution uses recursion, then the worst case space complexity is the depth of the tree, which could be as bad as O(n).

A tree O(1) space solution requires the used of Threaded Binary Tree, which I learned from other's solution. A threaded binary tree allows one to truly traverse a binary tree with constant space. In our case, we want a forward traversal, so the right child of any node who doesn't have a right child points to its in-order successor. Since we want to preserve the structure, we make that pointing on the fly and recover it after that pointing after use. A threaded binary tree solution is as follows. Notice that we need to find the in-order predecessor of each node twice. The total complexity of finding in-order predecessor of all nodes is O(n), since it's easy to see that every edge is traversed only once. So it is not too bad.

	public class Solution {
	TreeNode first = null;
	TreeNode second = null;
	public void recoverTree(TreeNode root) {
	TreeNode prev = null;
	TreeNode cur = root;
	while (cur != null) {
	if (cur.left == null) {
	if (prev != null && prev.val > cur.val) {
	second = cur;
	if (first == null) {
	first = prev;
	}
	}
	prev = cur;
	cur = cur.right;
	} else {
	TreeNode pred = cur.left;
	while (pred.right != null && pred.right != cur) {
	pred = pred.right;
	}
	if (pred.right == null) {
	pred.right = cur;
	cur = cur.left;
	} else {
	pred.right = null;
	if (prev != null && prev.val > cur.val) {
	second = cur;
	if (first == null) {
	first = prev;
	}
	}
	prev = cur;
	cur = cur.right;
	}
	}
	}
	int temp = first.val;
	first.val = second.val;
	second.val = temp;
	}
	}

view raw constant space solution hosted with ❤ by GitHub