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.

Sergey Avtandilov · Accepted 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;
}

Raviteja Ainampudi · 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"

Viasat

Question d’entretien chez Viasat

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois