7
\$\begingroup\$

Looking for code-review, optimizations and best practices. This question is attributed to geeksforgeeks.

NOTE: Please help me verify space complexity, as I am creating TreeData objects in recursion. I believe it is \$\mathcal{O}(1)\$. Ignore the space-complexity of stack frames. Looking only for space occupied by TreeData. At any point there are only 3 TreeData objects. As frame is popped, the TreeData gets garbage collected. Please verify.

public class CheckBalancedTree<E> {

    private TreeNode<E> root;

    public CheckBalancedTree(List<E> items) {
        create(items);
    }

    private void create (List<E> items) {
        if (items.size() == 0) { throw new IllegalArgumentException("The list is empty."); }

        root = new TreeNode<>(items.get(0));

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

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

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode<E> 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);
                }
            }
        }
    }

    // create a binary tree.
    private static class TreeNode<E> {
        private TreeNode<E> left;
        private E item;
        private TreeNode<E> right;

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

    private static class TreeData {
        private int height;
        private boolean isBalanced; 

        TreeData(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    public boolean checkIfBalanced() {
        if (root == null) {
            throw new IllegalStateException();
        }
        return checkBalanced(root).isBalanced;
    }

    public TreeData checkBalanced(TreeNode<E> node) {
        if (node == null) return new TreeData(-1, true);

        TreeData tdLeft = checkBalanced(node.left);

        if (!tdLeft.isBalanced) return new TreeData(-1, false); // if boolean value is false, then no need to return the correct value for height.

        TreeData tdRight = checkBalanced(node.right);

        if (tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
            return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
        } 

        return new TreeData(-1, false); // if boolean value is false, then no need to return the correct value for height.
    }
}

public class CheckBalancedTreeTest {

    @Test
    public void testLeftSkewed() {
        /*     1
        *    /
        *   2
        *  /
        * 3  
        */
        Integer[] leftSkewed =  {1, 2, null, 3, null, null, null};
        CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(leftSkewed));
        assertFalse(cbt.checkIfBalanced());
    }


    @Test 
    public void testRightSkewed() {
        /* 1
        *   \
        *    2  
        *     \
        *      3
        */      
        Integer[] rightSkewed = {1, null, 2, null, null, null, 3 };
        CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(rightSkewed));
        assertFalse(cbt.checkIfBalanced());
    }

    @Test 
    public void testSuccessCase() {
        /*
         *          1
         *         / \
         *        2   3
         *       /\  
         *      4  5
         */
        Integer[] successCase = {1, 2, 3, 4, 5, null, null};
        CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(successCase));
        assertTrue(cbt.checkIfBalanced()); 
    }

    @Test
    public void testFailureCase() {
        /*         
         *         1
         *        / \ 
         *       2   3    
         *      / \    
         *     4   5
         *        / \ 
         *       6   7 
         */
        Integer[] failure = {1, 2, 3, 4, 5, null, null, null, null, 6, 7, null, null};
        CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(failure));
        assertFalse(cbt.checkIfBalanced());
    }
}
\$\endgroup\$
0

3 Answers 3

3
\$\begingroup\$

Although the space use of TreeData seems a prominent part of your question, perhaps you might be interested in an alternative algorithm that doesn't require TreeData at all, eliminating your concerns about space.

I suppose the reason for TreeData was to carry a boolean value in addition to height. Note that the value of height is completely irrelevant when the boolean is false. Also note that height is always >= 0. Based on this logic, you can refactor your existing algorithm:

  • Simply look for the height
  • When a branch is found to be not balanced, return a negative value
  • Instead of checking a boolean value, check if the returned height is negative

Taking your algorithm, and replacing the types and and the boolean checks, the implementation becomes this, and it still passes all your unit tests, without using TreeData objects:

private static final int UNBALANCED = -1;

public boolean checkIfBalanced() {
    if (root == null) {
        throw new IllegalStateException();
    }
    return checkBalanced(root) != UNBALANCED;
}

public int checkBalanced(TreeNode<E> node) {
    if (node == null) return 0;

    int tdLeft = checkBalanced(node.left);

    if (tdLeft == UNBALANCED) return UNBALANCED;

    int tdRight = checkBalanced(node.right);

    if (tdRight != UNBALANCED && Math.abs(tdLeft - tdRight) <= 1) {
        return Math.max(tdLeft, tdRight) + 1;
    }

    return UNBALANCED;
}

I would make a few more improvements on top that:

  • The case of root == null is not necessarily an anomaly, but simply an empty tree. I think it makes sense to simply drop that check. The implementation will return true in this case, which is correct: an empty tree is balanced

  • The repeated return UNBALANCED is a bit ugly, duplicated code. They can be eliminated by using nested if statements, where only the balanced case will reach the innermost statement, and everything else will fall back to a final default return UNBALANCED statements. As the code will become a bit arrow shaped, it might be arguable whether it's really an improvement. See below, and I'll let you decide that for yourself.

  • With the logic refactored, now different names will make more sense for the functions and the local variables

  • It's recommended to always use braces, when an if has only a single statement

So the code becomes:

private static final int UNBALANCED = -1;

public boolean checkIfBalanced() {
    return getHeight(root) != UNBALANCED;
}

public int getHeight(TreeNode<E> node) {
    if (node == null) {
        return 0;
    }

    int leftHeight = getHeight(node.left);
    if (leftHeight != UNBALANCED) {
        int rightHeight = getHeight(node.right);
        if (rightHeight != UNBALANCED) {
            if (Math.abs(leftHeight - rightHeight) < 2) {
                return 1 + Math.max(leftHeight, rightHeight);
            }
        }
    }

    return UNBALANCED;
}
\$\endgroup\$
4
\$\begingroup\$
  1. From an algorithmic point of view TreeData actually uses \$\mathcal{O}(1)\$ space. However, the statement that it gets garbage collected when the reference to it no longer exists is not correct. It can be garbage collected much later(or even never).

  2. About code style. There are some inconsistencies in your code. When the if statement body consists of an only one statement, sometimes you put on the same line without using brackets, like here: if (node == null) return new TreeData(-1, true);, but sometimes you do start a new line and use brackets:

    if (tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
        return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
    } 
    

    I would recommend using the latter(or, at least, stick to one style, do not mix them).

  3. The amount of blank lines inside one method seems to be too big.

    root = new TreeNode<>(items.get(0));
    
    final Queue<TreeNode<E>> queue = new LinkedList<>();
    queue.add(root);
    
    final int half = items.size() / 2;
    
    for (int i = 0; i < half; i++) {
    

    It looks better this way:

    root = new TreeNode<>(items.get(0));
    final Queue<TreeNode<E>> queue = new LinkedList<>();
    queue.add(root);
    final int half = items.size() / 2;
    for (int i = 0; i < half; i++) {
    
  4. It is also a good practice to write comments for all public classes and methods(they should tell what instances of this class represent or what this method does).

\$\endgroup\$
1
\$\begingroup\$

I might me mistaken, but I think that the space taken by TreeData is NOT \$\mathcal{O}(1)\$.

Consider this method:

public TreeData checkBalanced(TreeNode<E> node) {

    if (node == null) return new TreeData(-1, true);

    TreeData tdLeft = checkBalanced(node.left); // (1)

    if (!tdLeft.isBalanced) return new TreeData(-1, false); // if boolean value is false, then no need to return the correct value for height.

    TreeData tdRight = checkBalanced(node.right); // (2)

    if (tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
        return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
    } 

    return new TreeData(-1, false); // if boolean value is false, then no need to return the correct value for height.
}

The method may execute until (2), at which point there exists one TreeData object (created at (1)). Then checkBalanced() may execute again until (2), at which point there are already two TreeData objects (one from this execution and another from the previous execution that got pushed into the stack and has not still finished). Then another instance of the method starts, etc. So space complexity of TreeData objects is \$\mathcal{O}(n)\$, \$n\$ being the height of the tree, or \$\mathcal{O}(log(n))\$ if \$n\$ is the number of nodes.

That said, I think there are quite a few things that can be improved in this code, although they are not related to efficiency.

First, the naming. CheckBalancedTree is a very confusing name for a class. It sounds like a phrase to me, not like a noun. I think a better name would be just BinaryTree, since it is a binary tree after all. It just happens to have some methods to determine whether it is balanced or not.

Then there's the method checkBalanced(), which accepts a tree node as a parameter and returns some data about its subtree. I think the name analyzeTree() explains better what that method does. Also, this method acts only on the node passed as a parameter and its descendants, so it should be static.

items.isEmpty() is clearer than items.size() == 0.

checkBalanced method is a bit confusing, when it could be way more simple. This version is a bit less efficient, but has the same complexity:

private static TreeData analyzeTree(TreeNode node) {

    if (node == null) return new TreeData(-1, true);

    TreeData tdLeft = analyzeTree(node.left);
    TreeData tdRight = analyzeTree(node.right);

    int height = Math.max(tdLeft.height, tdRight.height) + 1;
    boolean isBalanced = tdRight.isBalanced
                        && tdLeft.isBalanced
                        && Math.abs(tdLeft.height - tdRight.height) <= 1;

    return new TreeData(height, isBalanced);

}
\$\endgroup\$
1
  • \$\begingroup\$ I agree with space complexity \$\endgroup\$ Feb 9, 2015 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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