Write an algorithm that determines if a binary tree is balanced or not.

A balanced binary tree is defined as one where for every node, its left and right subtrees differ in height by no more than 1.

Question

Write an algorithm that determines if a binary tree is balanced or not. 

A balanced binary tree is defined as one where for every node, its left and right subtrees differ in height by no more than 1.

Raviteja Ainampudi · Accepted Answer

temp = []

def check (root, temp):
    
    if not root:
        return        
    if root.l_child != None:
        if root.data < root.l_child.data:
            temp.append(False)
    if root.r_child != None:
        if root.data < root.l_child.data:
            temp.append(False)
    check(root.l_child, temp)
    check(root.r_child, temp)  
    temp.append(True)
    return temp

c = check(r, temp)
if all(c):
    print "Balanced"
else:
    print "Not Balanced"

Sergey Avtandilov · Answer

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isBalanced(root) {
  function check(node) {
    if (node === null) {
      return { height: 0, balanced: true };
    }

    const left = check(node.left);
    const right = check(node.right);

    const height = 1 + Math.max(left.height, right.height);
    const balanced =
      left.balanced &&
      right.balanced &&
      Math.abs(left.height - right.height) <= 1;

    return { height, balanced };
  }

  return check(root).balanced;
}

Viasat

Viasat Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches