Return the next right node

Question

Given a binary tree, return the next right node. This question is attributed to GeeksForGeeks.

For example, consider the following Binary Tree. Output for 2 is 6, output for 4 is 5. Output for 10, 6 and 5 is NULL.

              10
           /      \
          2         6
       /   \         \ 
     8      4          5

Looking for code-review, optimizations and best practices.

class TreeNodeRightMost {
    TreeNodeRightMost left;
    int item;
    TreeNodeRightMost right;

    TreeNodeRightMost(TreeNodeRightMost left, int item, TreeNodeRightMost right) {
        this.left = left;
        this.item = item;
        this.right = right;
    }
}


class BinaryTree {

    private TreeNodeRightMost root;

    public BinaryTree(List<Integer> items) {
        create(items);
    }

    private void create (List<Integer> items) {        
        root = new TreeNodeRightMost(null, items.get(0), null);

        final Queue<TreeNodeRightMost> queue = new LinkedList<TreeNodeRightMost>();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNodeRightMost current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNodeRightMost(null, items.get(left), null);
                    queue.add(current.left);
                }
                if (right < items.size() && items.get(right) != null) {
                    current.right = new TreeNodeRightMost(null, items.get(right), null);
                    queue.add(current.right);
                }
            }
        }
    }

    public TreeNodeRightMost getRoot() {
        return root;
    }
}



public final class FindRightMost {

    private FindRightMost() {}

    /**
     * If two nodes with the same values are present then the node with least depth on the left most side
     * is considered.
     */
    public static Integer findRight (BinaryTree tree, int val) {
        final TreeNodeRightMost root = tree.getRoot();

        if (root == null) throw new IllegalStateException(" empty tree is not permitted");

        Queue<TreeNodeRightMost> queue = new LinkedList<>();
        Queue<TreeNodeRightMost> queueNext = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNodeRightMost node = queue.poll();

            if (node.item == val) {
                if (queue.size() > 0) {
                    return queue.poll().item;
                } else {
                    return null; 
                }
            }


            if (node.left != null) queueNext.add(node.left);
            if (node.right != null) queueNext.add(node.right);

            if (queue.isEmpty()) {
                queue = queueNext;
                queueNext = new LinkedList<>();
            }
        }

        throw new IllegalArgumentException("Dude !! your input was not present in the tree");
    }
}

public class FindRightMostTest {

    @Test
    public void test1() {
        /**
         * Simple tree with just 1 node
         */
        BinaryTree btree1 = new BinaryTree(Arrays.asList(1));
        assertNull(FindRightMost.findRight(btree1, 1));
    }

    @Test
    public void test2() {
        /** 
         *        10
         *      /    \
         *     5       18
         *    / \     / \
         *   4   6   17   19
         */
        BinaryTree btree2 = new BinaryTree(Arrays.asList(10, 5, 18, 4, 6, 17, 19));
        assertEquals(18, (int)FindRightMost.findRight(btree2, 5));
        assertNull(FindRightMost.findRight(btree2, 18));
        assertEquals(6,  (int)FindRightMost.findRight(btree2, 4));
        assertEquals(17, (int)FindRightMost.findRight(btree2, 6));
        assertEquals(19, (int)FindRightMost.findRight(btree2,17));
        assertNull(FindRightMost.findRight(btree2, 19));
    }


    @Test
    public void test3() {
        /**
         *               1
         *           /      \
         *      null          2
         *     /   \         /   \
         *   null  null    null    3
         */
        BinaryTree btree3 = new BinaryTree(Arrays.asList(1, null, 2, null, null, null, 3));
        assertNull(FindRightMost.findRight(btree3, 1));
        assertNull(FindRightMost.findRight(btree3, 2));
        assertNull(FindRightMost.findRight(btree3, 3));
    }

    @Test
    public void test4() {
        /**
         *                 4
         *             /     \ 
         *          2          null
         *       /   \        /    \
         *      1    null  null    null
         */
        BinaryTree btree4 = new BinaryTree(Arrays.asList(4, 2, null, 1, null));
        assertNull(FindRightMost.findRight(btree4, 2));
        assertNull(FindRightMost.findRight(btree4, 1));
    }

    @Test
    public void test5() {

        /**
         *             1
         *     2            3      
         *  4     null   null    7 
         * 
         */
        BinaryTree btree5 = new BinaryTree(Arrays.asList(1, 2, 3, 4, null, null, 7));
        assertNull(FindRightMost.findRight(btree5, 1));
        assertEquals(3, (int)FindRightMost.findRight(btree5, 2));
        assertNull(FindRightMost.findRight(btree5, 3));
        assertEquals(7, (int)FindRightMost.findRight(btree5, 4));
        assertNull(FindRightMost.findRight(btree5, 7));
    }

}

Answer 1

Just reviewing the findRight() method since many of the Node and other constructs have been reviewed in other questions of yours, and there's not much changed since then...

public static Integer findRight (BinaryTree tree, int val) {
    final TreeNodeRightMost root = tree.getRoot();

    if (root == null) throw new IllegalStateException(" empty tree is not permitted");

    Queue<TreeNodeRightMost> queue = new LinkedList<>();
    Queue<TreeNodeRightMost> queueNext = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNodeRightMost node = queue.poll();

        if (node.item == val) {
            if (queue.size() > 0) {
                return queue.poll().item;
            } else {
                return null; 
            }
        }


        if (node.left != null) queueNext.add(node.left);
        if (node.right != null) queueNext.add(node.right);

        if (queue.isEmpty()) {
            queue = queueNext;
            queueNext = new LinkedList<>();
        }
    }

    throw new IllegalArgumentException("Dude !! your input was not present in the tree");
}

Your code takes an int argument, but returns an Integer. These things have been discussed before. Your actual nodes contain an int, so you need to find a better solution to the mixing of primitive and Object types.

There is a simpler way to do this using a single queue, and adding a null value to the queue to mark the end-of-line for the tree. This saves having to swap the queue and queueNext instances.

You throw an exception with a space as the first character, and it's not well formatted.... if (root == null) throw new IllegalStateException(" empty tree is not permitted");... additionally, it is a 1-liner statement without using {} braces. These are things that have been said before, but don't seem to be sinking in. You use 1-liner if-blocks for the left and right adds as well.

The 'Dude!' exception is cheesy, and not relevant.

Consider the alternate code:

public static Integer findRight (BinaryTree tree, Integer val) {
    final TreeNodeRightMost root = tree.getRoot();

    if (root == null) {
        throw new IllegalStateException("Empty trees are not permitted");
    }

    Queue<TreeNodeRightMost> queue = new LinkedList<>();
    queue.add(root);
    queue.add(null);

    while (!queue.isEmpty()) {

        TreeNodeRightMost node = queue.poll();
        if (node == null) {
            // reached the end of a level.
            if (!queue.isEmpty()) {
                queue.add(null);
            }
        } else {

            if (val.equals(node.item)) {
                 TreeNodeRightMost ret = queue.poll();
                 return ret != null ? ret.item : null;
            }

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }

        }
    }

    throw new IllegalArgumentException("Your input was not in the tree");
}

Answer 2

A minor bug: You get an IndexOutOfBoundsException for an empty list in BinaryTree.create(List<Integer> items). You don't have a comment stating you need to input a list containing at least something. Consider returning IllegalArgumentException and adding a comment.