A BST has two nodes swapped. Figure out which two nodes. Looking for code-review, optimizations and best practices.
public class SwappedNodes {
private TreeNode root;
SwappedNodes(List<Integer> items) {
create(items);
}
private void create (List<Integer> items) {
if (items.isEmpty()) {
throw new IllegalArgumentException("The item is empty");
}
root = new TreeNode(items.get(0));
final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode current = queue.poll();
int left = 2 * i + 1;
int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(right));
queue.add(current.right);
}
}
}
}
private static class TreeNode {
private TreeNode left;
private int item;
private TreeNode right;
TreeNode (int item) {
this.item = item;
}
}
private static class PrevNode {
private TreeNode prevNode;
PrevNode (TreeNode prevNode) {
this.prevNode = prevNode;
}
}
/**
* Returns the 2 nodes which if swapped results in binary search tree.
*/
public int[] getSwappedNode( ) {
final List<TreeNode> list = new ArrayList<>();
computeSwappedNodes (root, new PrevNode(null), list);
int[] result = {list.get(0).item, list.get(list.size() - 1).item};
return result;
}
private void computeSwappedNodes (TreeNode node, PrevNode prevNode, List<TreeNode> list) {
if (node == null) return;
computeSwappedNodes (node.left, prevNode, list);
if (prevNode.prevNode != null) {
if (prevNode.prevNode.item > node.item) {
list.add(prevNode.prevNode);
list.add(node);
}
}
prevNode.prevNode = node;
computeSwappedNodes (node.right, prevNode, list);
};
}
public class SwappedNodesTest {
// both values in different branches
@Test
public void testDifferentBranches() {
SwappedNodes sn1 = new SwappedNodes(Arrays.asList(10, 4, 25, 2, 20, 8, null));
int[] a1 = {20, 8};
assertArrayEquals(a1, sn1.getSwappedNode());
}
// parent child relationship
@Test
public void testParentChild() {
SwappedNodes sn3 = new SwappedNodes(Arrays.asList(10, 2, 20, 5, 8, 15, 29));
int[] a3 = {5, 2};
assertArrayEquals(a3, sn3.getSwappedNode());
}
@Test
public void testAncestor() {
SwappedNodes sn4 = new SwappedNodes(Arrays.asList(8, 5, 20, 2, 10, 15, 29));
int[] a4 = {10, 8};
assertArrayEquals(a4, sn4.getSwappedNode());
}
}
