Problem:
We start with a binary search tree (BST), that has 2 elements swapped out of order. Design an algorithm to recover the tree without changing its structure.
Example:
Input:
3
/ \
1 4
/ \
2 5
Output:
2
/ \
1 4
/ \
3 5
Solution:
We can convert the tree to an inorder traversal array, find the out of order elements, then go back to the original tree, find the 2 nodes, then swap the value.
It is worth studying the classical one path algorithm for finding the 2 swapped elements in an almost ordered array. The same principle can be used to find the 2 swapped elements in the tree without first converting it into an array.
import java.util.*;
class Solution {
Node x = null;
Node y = null;
Node pre = null;
public static void main(String...args) {
Node root = new Node(3, new Node(1, null, null),
new Node(4, new Node(2, null, null), new Node(5, null, null))
);
inOrder(root);
System.out.println();
Solution so = new Solution();
so.findDisOrders(root);
so.swap();
inOrder(root);
System.out.println();
}
private static void inOrder(Node root) {
if(root == null) return;
inOrder(root.left);
System.out.print(root.value + " ");
inOrder(root.right);
}
private void swap() {
int val = x.value;
x.value = y.value;
y.value = val;
}
private void findDisOrders(Node root) {
if(root == null) return;
findDisOrders(root.left);
if(pre != null && pre.value > root.value) {
y = root;
if(x == null)
x = pre;
else
return;
}
pre = root;
findDisOrders(root.right);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
class Solution {
Node x = null;
Node y = null;
Node pre = null;
public static void main(String...args) {
Node root = new Node(3, new Node(1, null, null),
new Node(4, new Node(2, null, null), new Node(5, null, null))
);
inOrder(root);
System.out.println();
Solution so = new Solution();
so.findDisOrders(root);
so.swap();
inOrder(root);
System.out.println();
}
private static void inOrder(Node root) {
if(root == null) return;
inOrder(root.left);
System.out.print(root.value + " ");
inOrder(root.right);
}
private void swap() {
int val = x.value;
x.value = y.value;
y.value = val;
}
private void findDisOrders(Node root) {
if(root == null) return;
findDisOrders(root.left);
if(pre != null && pre.value > root.value) {
y = root;
if(x == null)
x = pre;
else
return;
}
pre = root;
findDisOrders(root.right);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time complexity is O(N) because we have to visit the N nodes. The space complexity is O(1).
