Find all nodes in tree, without a sibling

Question

Find all nodes of trees, without siblings.

This question is attributed to GeeksForGeeks.

I'm looking for code reviews, optimizations and best practices.

  public class PrintNodesWithoutSiblings<T> {

        private TreeNode<T> root;

        public PrintNodesWithoutSiblings(List<T> items) { 
            create(items);
        }

        private void create (List<T> items) {
            root = new TreeNode<T>(items.get(0));

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

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

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

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

        private static class TreeNode<T> {
            private TreeNode<T> left;
            private T item;
            private TreeNode<T> right;

            TreeNode(T item) {
                this.item = item;
            }
        }


        public List<T> nonSiblingNodes() {
            if (root == null) {
                throw new IllegalStateException("Empty tree. Tree cannot be empty.");
            }

            final List<T> list = new ArrayList<T>();
            findNonSiblingNodes(root, list);
            return list;
        } 


        private void findNonSiblingNodes(TreeNode<T> node, List<T> list) {
            if (node == null) {
                return;
            }

            if (node.left != null && node.right != null) {
                findNonSiblingNodes(node.left, list);
                findNonSiblingNodes(node.right, list);
            } else if (node.left != null) {
                list.add(node.left.item);
                findNonSiblingNodes(node.left, list);
            } else if (node.right != null) {
                list.add(node.right.item);
                findNonSiblingNodes(node.right, list);
            }
        }
    }


    public class PrintNodesWithoutSiblingTest {


        @Test
        public void test1() {
            PrintNodesWithoutSiblings<Integer> ps1 = new PrintNodesWithoutSiblings<Integer>(Arrays.asList(1, 2, 3, 4, null, 6, null));
            assertTrue(Arrays.asList(4, 6).equals(ps1.nonSiblingNodes()));
        }

        @Test
        public void test2() {
            PrintNodesWithoutSiblings<Integer> ps2 = new PrintNodesWithoutSiblings<Integer>(Arrays.asList(1, 2, null, 4, null, null, null));
            assertTrue(Arrays.asList(2, 4).equals(ps2.nonSiblingNodes()));
        }
    } 

Answer 1

Recursion

The null-check in your recursive method is redundant. The preliminary checks and the mid-recursion checks ensure that the method is never called with a null input.

I also really favour a simplified recursive approach, where the recursion checks it's own conditions, instead of pre-checking the recursive conditions before calling the recursion. In this case, it halves the number of recursive calls, halves the list.adds, and reduces by a third the number of if-conditions in your code:

    private void findNonSiblingNodes(TreeNode<T> node, boolean hasSibling List<T> list) {
        if (node == null) {
            return;
        }

        if (!hasSibling) {
            list.add(node);
        }

        findNonSiblingNodes(node.left, node.right != null, list);
        findNonSiblingNodes(node.right, node.left != null, list);
    }

You would call that code with:

    public List<T> nonSiblingNodes() {
        final List<T> list = new ArrayList<T>();
        findNonSiblingNodes(root, true, list);
        return list;
    } 
}

It is safe to remove the null-check on the root node, because it can never be null at that point. That's because ....

Bugs

... your code does horrible things in the constructor, which will fail before it gets here:

    public PrintNodesWithoutSiblings(List<T> items) { 
        create(items);
    }

    private void create (List<T> items) {
        root = new TreeNode<T>(items.get(0));
        ....

Your constructor will throw NPE if the items is null, and will throw NoSuchElementException if the List is empty. Thus, the root will never be null in the recursion.

Style

final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();

You should use the 'diamond operator' when using Java7 and later. The line above can be just:

final Queue<TreeNode<T>> queue = new LinkedList<>();

Similarly, the line:

final List<T> list = new ArrayList<T>();

can be:

final List<T> list = new ArrayList<>();

Answer 2

Data Structures vs. Methods to operate on them

A pattern I commonly see in your code is that whenever you're supposed to do an operation on a tree, you end up implementing the tree plus adding the operation itself.

Your code would be a lot simplified if you re-used the same data structures. For this code assignment, I would like to see your code as:

public static List<T> findNonSiblingNodes(BinaryTree<T> tree) {
    ... perform operations and return results ...
}

This would force you to do proper separation of concerns, which adheres to the single responsibility principle.

It would also greatly reduce bugs in your code because of reduced code duplication and not have us mention some things over and over again.

As an example of code duplication, compare your create method in the code you have for this question with your create method in Given a BST, transform it into greater sum tree, and in Detect if a tree is a complete binary tree. It is the same code! All of these assignments would greatly benefit from using a shared BinaryTree (or BinarySearchTree) implementation.

I like that you in this code have made TreeNode generic with TreeNode<T>, this is a great start for a shared BinaryTree implementation.

If you need any help with this, or want suggestions on how to structure your code/projects, don't be afraid to drop by in The 2nd Monitor. We don't bite.

Answer 3

Tests

I will say it again and again and again! Tests are important!! Don't throw 2 tests that are, sorry to say it, really bad. You should use them like powerful tools that will help you create better code. If you don't put effort on them, then don't bother to make them.

    @Test
    public void test1() {
        PrintNodesWithoutSiblings<Integer> ps1 = new PrintNodesWithoutSiblings<Integer>(Arrays.asList(1, 2, 3, 4, null, 6,  null));
        assertTrue(Arrays.asList(4, 6).equals(ps1.nonSiblingNodes()));
    }

test1 is really a bad name. I've already point it out in other review, so I will not extend on that. But you've added a new things here, you used assertTrue() to test the equality of the two lists. Why? You've already used assertEquals, why would you not use it? Since what you really want is to verify that those lists are equal.

There is nothing more to say for those tests than what I've already said in my previous answer. Add more tests, do them carefully and put the same effort that you would for your algo.