Balanced Binary Tree Coding Interview Question

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.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Read More: Median of Two Sorted Arrays Coding Challenge
Read More: Top Three React Chart Library
Read More: Parenthesis Matching Interview Question

First We will Add code for how to create Binary tree in Javascript

Here, we will create the tree node. 

class treeNode {
  constructor(data) {
    this.node = data;
    this.left = null;
    this.right = null;
  }
}

Now we can use tree node to insert in Tree. Now we will create the class which will have insert node method.

class binrayTree {
  
  constructor() {
    this.root = null;
  }

  insertNode(data) {
    
    let newnode = new treeNode(data);
    let currnode;
    if (!this.root) {
      this.root = newnode;
    } else {
      currnode = this.root;
    }
 
    while (currnode) {
      if (data < currnode.node) {
        if (!currnode.left) {
          currnode.left = newnode;
          break;
        } else {
          currnode = currnode.left;
        }
     } else if (data > currnode.node) {
       if (!currnode.right) {
         currnode.right = newnode;
         break;
       } else {
         currnode = currnode.right;
       }
     } else {
       console.log('Ignoring this value as the BST supposed to be a tree containing UNIQUE values');
        break;
      }
    }
  }
}

Let’s test out this code by inserting node.

let newitem = new binrayTree();
newitem.insertNode(8);
newitem.insertNode(3);
newitem.insertNode(10);
newitem.insertNode(1);
newitem.insertNode(6);
newitem.insertNode(14);
newitem.insertNode(4);
newitem.insertNode(7);
newitem.insertNode(9);
newitem.insertNode(11);
newitem.insertNode(12);
console.log(newitem);

A binary tree in which the left and right subtrees of every node differ in height by no more than 1. As per this definition we need to create the function to verify height of left and right subtree and return difference.

const maxDepth = (treeroot) => {
  if (treeroot === null) {
    return 0;
  }
  return 1 + Math.max(maxDepth(treeroot.left), maxDepth(treeroot.right));
}

const minDepth(treeroot) {
  if (treeroot === null) {
    return 0;
  }
  return 1 + Math.min(minDepth(treeroot.left), minDepth(treeroot.right));
}

const isBalanced = (treeroot) => {
  return (maxDepth(treeroot) - minDepth(treeroot) <= 1);
}
console.log(isBalanced(newitem.root));