0
\$\begingroup\$

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

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Is this an assignment from geeksfromgeeks? \$\endgroup\$ – Simon Forsberg Aug 30 '14 at 10:48
3
\$\begingroup\$
computeSwappedNodes (root, new PrevNode(null), list);

Unneeded space between function name and parentheses with arguments. You do this multiple times.

/**
 * Returns the 2 nodes which if swapped results in binary search tree.
 */
public int[] getSwappedNode( ) {

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.