CODEWITHSUNDEEP
javatree
Srinivas
Srinivas

Reputation: 9

Balanced binary tree returning true

I am trying to solve a question of the balanced binary tree.

Given a binary tree : [1,2,2,3,3,null,null,4,4]. Determine if it's a balanced tree or not.

And I had the solution: 



    public boolean isBalanced(TreeNode root) {

            int height = heightCalculation(root);
            if(height > 1) return false;
            else 
                return true;
        }    
            public int heightCalculation(TreeNode root){

             if(root == null)
                return 0;



            int left_height = Integer.MIN_VALUE;
            int right_height = Integer.MIN_VALUE;

                left_height = heightCalculation(root.left);
                right_height =heightCalculation(root.right);

           return Math.abs(left_height - right_height);

            }

The tree structure looks like:

      1
      / \
     2   2
    / \
   3   3
  / \
 4   4

It's returning true but the actual answer is false. Can someone help me in fixing the issue ? I have kept the tree structure for your reference

Upvotes: 0

Views: 68

Answers (1)

bodha
bodha

Reputation: 180

The problem is that the heightCalculation function which is supposed to calculate the heights of right and left sub-trees and find the difference always returns 0. Following is the correct implementation for calculating the height of a binary tree:

int height(TreeNode node) {
    if(node == null) {
        return 0;
    } else {
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

Use the above function to find the heights of the sub trees and then calculate the difference.

Upvotes: 1

Related Questions