Balanced Binary Tree in Java

Good news! It seems that vaccination against COVID-19 is already in progress in several parts of the country. At this time vaccination is limited to the elder and to first responders. General public vaccination will start in spring 2021. In the mean time pharmacies will start preparing with equipment, procedures and protocols to get two shots of the vaccine per patient. Hopefully all will proceed with minor hiccups.

I randomly selected LeetCode problem 110 Balanced Binary Tree.

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node 
differ in height by no more than 1.

Constraints:

o The number of nodes in the tree is in the range [0, 5000].
o -104 <= Node.val <= 104

We are given a binary tree and we are asked to check if it is balanced or not and return true or false if not. A balanced tree is when all the subtrees in the binary tree differ in depth by no more than one.

Not sure what to do regarding the constraints. If you come up with something that would take advantage of such information please let me know.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        
    }
}

The signature for the function / method of interest is simple. We are provided with a binary tree, we figure out if the tree is balanced and return true or false.

I will solve this problem using Java on my Windows 10 computer using the VSCode IDE. When I believe to have a solution candidate I will copy the necessary code to the LeetCode IDE and will run it. If the code passes, then I will submit it. The code in this post passed all tests and was accepted.

3,9,20,null,null,15,7
main <<<  strArr: [3, 9, 20, null, null, 15, 7]
main <<<     arr: [3, 9, 20, null, null, 15, 7]
main <<< inOrder: 9 3 15 20 7
<<< root: 3 leftH: 1 rightH: 2
<<< root: 9 leftH: 0 rightH: 0
<<< root: 20 leftH: 1 rightH: 1
<<< root: 15 leftH: 0 rightH: 0
<<< root: 7 leftH: 0 rightH: 0
main <<<  output: true


1,2,2,3,3,null,null,4,4
main <<<  strArr: [1, 2, 2, 3, 3, null, null, 4, 4]
main <<<     arr: [1, 2, 2, 3, 3, null, null, 4, 4]
main <<< inOrder: 4 3 4 2 3 1 2
<<< root: 1 leftH: 3 rightH: 1
main <<<  output: false

I need to develop a test scaffolding to replicate the services provided by LeetCode to check the proposed solutions.

Our test code seems to accept a line holding the values or the node in a breadth first search.

After the line is read we split it into a string array and display it. We proceed by processing the string array and generating an integer array which we also display.

Apparently we load the data in the array into a binary tree. We then perform an in order traversal. As I am writing this post, I think it would have been better a breadth first traversal. Sorry about that. If you follow the two examples with the associated diagrams provided by LeetCode (as I did) it should make sense. At this point we have generated the proper binary try associated with the input data.

It seems that we then call the function that determines if the binary tree is or is not balanced. We will discuss the messages generated by the function when we go over the actual code.

Finally our test scaffolding displays the value returned by the function in question. The output seems to match the expected results of the two examples. By looking at the diagrams of the binary trees provided by LeetCode we should be able to determine that in the first case the tree is balanced while in the second is not.

/**
 * Represents a node in the binary tree.
 */
class TreeNode {

    // **** class members ****
    int val;
    TreeNode left;
    TreeNode right;

    // **** constructor(s) ****
    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    // **** ****
    @Override
    public String toString() {
        return "" + this.val;
    }
}

This is the class that we should use for the binary tree implementation. I had to implement it in the code to be able to build the binary trees. Not sure why I made a copy of the code for the post. If you look or get the code at the associated GitHub repository with this post the entire code is available for review and experimentation.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read binary tree dfs data ****
        String[] strArr = br.readLine().trim().split(",");

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<<  strArr: " + Arrays.toString(strArr));

        // **** create and populate Integer array ****
        Integer[] arr = new Integer[strArr.length];
        for (int i = 0; i < strArr.length; i++) {
            if (strArr[i].equals("null"))
                arr[i] = null;
            else
                arr[i] = Integer.parseInt(strArr[i]);
        }

        // ???? ????
        System.out.println("main <<<     arr: " + Arrays.toString(arr));

        // **** create and populate binary tree ****
        TreeNode root = populateTree(arr);

        // ???? ????
        System.out.print("main <<< inOrder: ");
        inOrder(root);
        System.out.println();

        // **** compute and display if binary tree is balanced ****
        System.out.println("main <<<  output: " + isBalanced(root));
    }

This is the test code used to input the data, parse it and generate a binary tree. At that point we can call the isBalanced() function / method and display the returned value. Of course the test scaffolding IS NOT PART OF THE SOLUTION.

The idea for the function is to check the depth of the binary tree at different nodes. If in any node the depth of the left sub tree differs to the one from the right sub tree for more than 1 then the binary tree is NOT balanced. Given this approach we will have to compute the depth of a binary tree in an auxiliary or utility function.

A few months ago I generated the Maximum Depth of a Binary Tree post. In a nutshell we descend on the left sub tree computing the depth. Then we repeat the process on the right sub tree all these while keeping track of the maximum depth. When done we return the maximum depth.

    /**
     * Compute depth of binary tree.
     * Utility function.
     * Recursive call O(n).
     */
    static int depth(TreeNode root) { 

        // **** base case ****
        if (root == null) 
            return 0; 

        // **** recursive call ****
        return 1 + Math.max(depth(root.left), depth(root.right)); 
    }

The code we used is similar to the one on the previous post. The only difference is that the different steps have been condensed in an attempt to reduce execution time.

We start by calling the depth() function at the root. At each node we recursively call the function on the left and right sub trees. We get the maximum depth of the pair and add 1 to take into account each call.

    /**
     * Given a binary tree, determine if it is height-balanced.
     * Recursive call O(n).
     * 
     * Runtime: 1 ms, faster than 46.61% of Java online submissions.
     * Memory Usage: 41.9 MB, less than 5.01% of Java online submissions.
     */
    static boolean isBalanced(TreeNode root) {

        // **** base condition ****
        if (root == null)
            return true;

        // **** get the depth of the left and right sub trees O(n) ****
        int leftH   = depth(root.left);
        int rightH  = depth(root.right);

        // ???? ????
        System.out.println("<<< root: " + root.val + " leftH: " + leftH + " rightH: " + rightH);

        // **** recursive calls O(n) ****
        if (Math.abs(leftH - rightH) <= 1 
            && isBalanced(root.left)
            && isBalanced(root.right))
            return true;
        else
            return false;
    }

This is also a recursive call. We start by computing the depth of the left and right sub trees of the root node. If the difference in depths is > 1 the binary tree is not balanced. If it is then we check if the left sub tree and then the right sub tree are balanced.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 5,055 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.