How to store depth of Binary Search Tree

Question

I'm trying to determine if a Binary Search Tree is balanced. I'm not too clear on how to store the depth of the childnodes of the left and right branch. I'm trying to return true if the right branch is greater than the left branch by a length of a max of 1 and vice versa.

 /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
/**
     * @param {TreeNode} root
     * @return {boolean}
     */

var isBalanced = function(root) {
  var checkChild = function(root) { 
    if (this.left) {
      var left = 1;
      this.left.checkChild(root);
      if (this.right) {
        left += 1;
        this.right.checkChild(root);
      }
      if (this.right) {
        var right = 1;
        this.right.checkChild(root);
        if (this.left) {
          right += 1;
          this.right.checkChild(root);
        }
      }
    }
    if (left - right > 1 || right - left > 1) {
      return false;
    }
    return true;
  };
};

I was thinking of creating a var to increment every-time a node is traversed for both the right and left branches starting from the head. But I'm realizing that this will compare the total number of nodes from the left branch to the total number of nodes on the right branch, which won't work.

Answer 1

If you want to use checkChild as a method, you should define it as such, not as a variable. I would also suggest to not return a boolean, but the real difference in depth between left and right subtree. This will give more information to the caller, who can still treat that value as a boolean if so desired (falsy means balanced, truthy means tilted).

Here is how your implementation could look:

class TreeNode {
    constructor(val) {
        this.val = val;
    }
    add(node) {
        const dir = node.val < this.val ? "left" : "right";
        if (this[dir]) {
            this[dir].add(node);
        } else {
            this[dir] = node;
        }
    }
    height() {
        return Math.max(
            this.left ? this.left.height() + 1 : 0,
            this.right ? this.right.height() + 1 : 0
        );
    }
    tilt() {
        return (this.left  ? this.left.height() + 1 : 0)
             - (this.right ? this.right.height() + 1 : 0);
    }
    static from(...data) {
        if (!data.length) return;
        const root = new TreeNode(data[0]);
        for (let v of data.slice(1)) {
            root.add(new TreeNode(v));
        }
        return root;
    }
}

const root = TreeNode.from(13, 4, 9, 16);
console.log(root);
console.log('Tilt at root = ', root.tilt());

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

At first find max depth of the root, then find min depth of the root. It is easy using dfs. Next step is to check difference of these depths. The code will look like this:

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}

var isBalanced = function(root) {
    var foo = function(root, fun) {
        if (root === null) return 0
        l = foo(root.left, fun)
        r = foo(root.right, fun)
        return fun(l, r);
    }
    return foo(root, Math.max) - foo(root, Math.min) < 2
}

let tree = new Node(1)
tree.left = new Node(2)
tree.left.left = new Node(3)
tree.left.left.left = new Node(4)
tree.right = new Node(5)
tree.right.left = new Node(6)
document.write(isBalanced(tree))

Answer 3

At each check why are you sending the head again like why root again? this.left.checkChild(root)

Instead, if you want to find the depth, your implementation should look something like this:

function treeDepth(tree) 
{
   if (tree === null) 
       return 0;
   else
   {
       /* compute the depth of each subtree */
       let leftDepth = treeDepth(tree.left);
       let rightDepth = treeDepth(tree.right);

       /* use the larger one */
       if (leftDepth > rightDepth) 
           return(leftDepth+1);
       else return(rightDepth+1);
   }
}