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

Pergunta de entrevista da empresa Viasat

Respostas da entrevista

Empresas seguidas

Buscas de vagas