# Find swapped nodes in BST

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>();

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));
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(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) {
}
}

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());
}

}

• Is this an assignment from geeksfromgeeks? Commented Aug 30, 2014 at 10:48

computeSwappedNodes (root, new PrevNode(null), list);

/**

No, you return the items stored within. Not the nodes. You don't fulfill the assignment as stated. Additionally, you return multiple nodes, so name the method getSwappedNodes. Lastly, no need for a space in an empty set of parentheses.