Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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()));
        }
    } 
share|improve this question

3 Answers 3

up vote 8 down vote accepted

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<>();
share|improve this answer

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.

share|improve this answer
    
"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. " - Since I am practicing for interviews, most of the answers are tailored to how I would write on white board. Thus in any interview round there would be 1 question of tree, at one point in time, on the white board. Thus resusability works in real life wont work for interviews. –  JavaDeveloper Jul 7 at 20:10
    
@JavaDeveloper Sure, but if you get this question at an interview, it would not make that good impression to make it in the same class and name it like you do. Besides, once you actually get the job (or a job) then you are faced with real life so it is a good idea to practice it. It's still important with separation of concerns. –  Simon André Forsberg Jul 7 at 20:32
    
I understand, but on the other hand I have also seen Linkedlist.java do the same, and I want to replicate that. I would say you had a good feedback, and I see great advantages but just opting the other way. Thanks –  JavaDeveloper Jul 8 at 0:28
    
@JavaDeveloper I fail to see the connection between what you're doing and LinkedList.java. The LinkedList is a data structure, what you're mostly implementing is methods that are supposed to do work on a data structure. –  Simon André Forsberg Jul 8 at 18:27
    
@JavaDeveloper The choice is yours, it is your code. Just remember that if you keep doing what you have always done, you will get the same results that you have always gotten. –  Simon André Forsberg Jul 8 at 18:28

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 use assetEquals, 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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