Complete the function isBalanced() to take in a root node of a binary tree and r
ID: 3715838 • Letter: C
Question
Complete the function isBalanced() to take in a root node of a binary tree and return True if the tree is balanced, False otherwise.
Let's define the criteria for a tree to be balanced if for every node in the tree, the difference in height between the left subtree and the right subtree of that node is no more than 1.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def isBalanced(root):
# TODO
root = Node(7)
root.left = Node(4)
root.left.left = Node(1)
root.left.right = Node(5)
"""
7
/
4 (NOT BALANCED)
/
1 5
"""
print(isBalanced(root)) # should print False
root.right = Node(10)
root.right.right = Node(13)
"""
7
/
4 10 (BALANCED)
/
1 5 13
"""
print(isBalanced(root)) # should print True
root.left.left.left = Node(0)
root.left.right = None
"""
7
/
4 10 (NOT BALANCED)
/
1 13
/
0
"""
print(isBalanced(root)) # should print False
Explanation / Answer
boolean isBalanced(Node root)
{
int lh; /* height of left subtree */
int rh; /* height of right subtree */
if (root == null)
return true; /*if tree is empty*/
lh = height(root.left); /* height of left sub tree */
rh = height(root.right); /* height of left sub tree */
if (Math.abs(lh - rh) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right))
return true;
return false;
}
int height(Node root) /* Computes the height of the tree */
{
if (root == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(root.left), height(root.right));
}