Balanced Binary Tree Solution

Question

I solved a problem in LeetCode for binary balanced tree and it's pretty basic. I've a doubt with the solution and here's what I did so far - Balanced Binary Tree. My attempt was as follows and luckily it got accepted:

static bool IsBalanced(BinaryTree root) {
    isBalanced = true;

    int chk = CheckBalance(root.Root, 0);

    return isBalanced;
  }

  static int CheckBalance(TreeNode root, int depth) {
    if (root == null)
      return 0;

    int left = CheckBalance(root.left, depth + 1);
    int right = CheckBalance(root.right, depth + 1);

    if (Math.Abs(left - right) > 1)
      isBalanced = false;
    return GetMax(left, right);
  }

  static int GetMax(int left, int right) {
    if (left > right)
      return left;
    else
      return right;
  }

1st Input:

       3
      / \
     9  20
        / \
       15  7

Output: True

2nd Input:

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

Output: False

For the first input, the tree is balanced and it returned true. But for the second one, it should return false as it isn't balanced. But with my sample input in the fiddle, returns true. Is it some kind of bug or error as I am doing recursive call for all possible trees?

Answer 1

First this:

In CheckBalance you never use depth. Since you say it works on the challenge site, I must assume you retyped the code and did not enter the same code here. The return statement for the base case should be:

return depth;

The main issue is however that your Add function creates node instances with value null. This means that for the second example input you actually create this tree:

            ___1___
           /       \
        __2__       2
       /     \     / \
      3       3 null null
     / \     / \
    4   4 null null

... and that tree is balanced!

It is not trivial to write an Add function that can do the job as expected, without keeping track of whether a null child was the default value, or was really populated with null. This difference determines where the next value should be inserted.

Therefore I would suggest a different approach. Provide a BinaryTree constructor that receives the whole input as an array, and which then iterates that array in a controlled way, inserting values where they are supposed to end up:

  public BinaryTree(int?[] data) {
    if (data.Length == 0) return;
    
    var queue = new Queue<TreeNode>();
    Root = new TreeNode(data[0]);
    queue.Enqueue(Root);
    
    for (int i = 1; i < data.Length; i++) {
      TreeNode presentNode = queue.Dequeue();
      if (data[i] != null) {
        presentNode.left = new TreeNode(data[i]);
        queue.Enqueue(presentNode.left);
      }
      i++;
      if (i >= data.Length) break;
      if (data[i] != null) {
        presentNode.right = new TreeNode(data[i]);
        queue.Enqueue(presentNode.right);
      }
    }
  }

Using this constructor, you can now run your test case like this:

    int?[] data = {1, 2, 2, 3, 3, null, null, 4, 4};  
    BinaryTree aBinaryTree = new BinaryTree(data);
    bool status = IsBalanced(aBinaryTree);