Interview Question

    Balanced Binary Tree Height

Taking a binary tree as an input, provide a function to return True if the tree is balanced.  The height of a balanced binary tree is defined to be any tree where every node's pair of subtrees do not differ in height by more than 1.

Write your answer as pseudocode to fit into the following:

class Node {
   def __init__(self, val, left=None, right=None) {
       self.val = val
       self.left = left
       self.right = right
   }
}
def is_balanced(tree) {
   # YOUR ANSWER HERE
}
# EXAMPLE 1
    1
   2 3
      4
balanced[4] = Node(4)
balanced[3] = Node(3, balanced[4])
balanced[2] = Node(2)
balanced[1] = Node(1, balanced[2], balanced[3])
print(is_balanced(balanced[1]))
# TRUE

# EXAMPLE 2
    1
   2
  3
unbalanced[3] = Node(3)
unbalanced[2] = Node(2, unbalanced[3])
unbalanced[1] = Node(1, unbalanced[2])
print(is_balanced(unbalanced[1]))
# FALSE


Answers

  • ▲
    2563
    ▼
    @qassim.mutawa 

    class Solution(object):
    def __init__(self):
        self.d = {}
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def depth(root):
            if not root: return 0
            if(root in self.d): return self.d[root]
            self.d[root] = 1 + max(depth(root.left), depth(root.right))
            return self.d[root]
        if not root: return True
        return abs(depth(root.left) - depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

  • ▲
    160
    ▼
    @shruti.kshirsagar912 

    def is_balanced(tree) {        
        int lh; /* for height of left subtree */
  
        int rh; /* for height of right subtree */
  
        /* If tree is empty then return true */
        if (node == null) 
            return true; 
  
        /* Get the height of left and right sub trees */
        lh = height(node.left); 
        rh = height(node.right); 
  
        if (Math.abs(lh - rh) <= 1
            && isBalanced(node.left) 
            && isBalanced(node.right)) 
            return true; 
  
        /* If we reach here then tree is not height-balanced */
        return false; 
}
int height(Node node) 
    { 
        /* base case tree is empty */
        if (node == null) 
            return 0; 
  
        /* If tree is not empty then height = 1 + max of left 
         height and right heights */
        return 1 + Math.max(height(node.left), height(node.right)); 
    }

  • ▲
    131
    ▼
    @shalabh.neema 

    if(tree==null)
return 0;

a=1+is_balanced(tree.left);
b=1+is_balanced(tree.right);

if(a>b)
return a;
else
return b;

  • ▲
    64
    ▼
    @ayindeesther698 

    2

  • ▲
    64
    ▼
    @theophilus.raymond 

    9

Interview Questions

This question was recently asked at a major tech company (ie Google, Apple, Facebook, Amazon)
We're compiling a definitive list of interview questions.

Take a practice interview and score yourself.

<< Return to Index