Challenge: Balanced Trees
A balanced tree, specifically a balanced Binary Search Tree (BST), is a tree data structure in which the heights of any node's left and right subtrees differ by at most one. This balance ensures efficient searching, insertion, and deletion operations, maintaining a logarithmic time complexity for these operations. In a balanced BST, the tree's height is minimized, leading to optimal performance.
Let's look at the example of unbalanced tree:
In the provided BST, the left subtree of the root node has a height of 4, while the right subtree has a height of only 2. This significant difference in heights indicates that the tree is unbalanced, leading to inefficient search, insertion, and deletion operations compared to a balanced BST.
Task
Swipe to start coding
You are provided with a Binary Search Tree (BST) implemented in Python. Your task is to write a function to determine whether the BST is balanced or not.
You have to perform the following steps:
- calculate the height of a subtree rooted at a given node recursively. It returns the maximum height between the left and right subtrees plus one (to account for the current node). This logic is implemented in
calculate_height()function. - Recursively check if the subtree rooted at a given node is balanced. It is implemented using the
is_balanced_recursive()function. It compares the heights of the left and right subtrees and returnsFalseif the difference in heights is greater than 1, indicating an imbalance. - To check if the tree is balanced, you must call the
is_balanced_recursive()with the tree root as an argument.
Solution
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class TreeNode:
def __init__(self, key):
# Initialize a new TreeNode with a given key value
self.key = key
self.left = None # Initialize left child pointer to None
self.right = None # Initialize right child pointer to None
class BST:
def __init__(self):
# Initialize an empty Binary Search Tree (BST) with no root
self.root = None
def insert(self, key):
# Insert a new key into the BST
if self.root is None: # If the tree is empty, create a new root node
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key) # Otherwise, call recursive insertion
def _insert_recursive(self, root, key):
# Recursively insert the key into the appropriate position in the tree
if key < root.key: # If the key is less than the current node's key, go left
if root.left is None: # If the left child is None, insert a new node
root.left = TreeNode(key)
else:
self._insert_recursive(root.left, key) # Otherwise, continue recursion to the left
elif key > root.key: # If the key is greater than the current node's key, go right
if root.right is None: # If the right child is None, insert a new node
root.right = TreeNode(key)
else:
self._insert_recursive(root.right, key) # Otherwise, continue recursion to the right
def is_balanced(self):
# Check whether the BST is balanced or not
# Returns True if balanced, False otherwise
def calculate_height(node):
Everything was clear?
Thanks for your feedback!
Section 4. Chapter 6
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class TreeNode:
def __init__(self, key):
# Initialize a new TreeNode with a given key value
self.key = key
self.left = None # Initialize left child pointer to None
self.right = None # Initialize right child pointer to None
class BST:
def __init__(self):
# Initialize an empty Binary Search Tree (BST) with no root
self.root = None
def insert(self, key):
# Insert a new key into the BST
if self.root is None: # If the tree is empty, create a new root node
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key) # Otherwise, call recursive insertion
def _insert_recursive(self, root, key):
# Recursively insert the key into the appropriate position in the tree
if key < root.key: # If the key is less than the current node's key, go left
if root.left is None: # If the left child is None, insert a new node
root.left = TreeNode(key)
else:
self._insert_recursive(root.left, key) # Otherwise, continue recursion to the left
elif key > root.key: # If the key is greater than the current node's key, go right
if root.right is None: # If the right child is None, insert a new node
root.right = TreeNode(key)
else:
self._insert_recursive(root.right, key) # Otherwise, continue recursion to the right
def is_balanced(self):
# Check whether the BST is balanced or not
# Returns True if balanced, False otherwise
def calculate_height(node):
# Calculate the height of the subtree rooted at the given node
if node is None: # Base case: if node is None, height is 0
return 0
return ___(calculate_height(node.left), calculate_height(node.right)) + 1 # Height is max of left and right subtrees, plus 1
def is_balanced_recursive(node):
# Recursively check if the subtree rooted at the given node is balanced
if node is None: # Base case: if node is None, subtree is balanced
return True
left_height = calculate_height(node.___) # Height of left subtree
right_height = calculate_height(node.___) # Height of right subtree
if abs(left_height - right_height) > 1: # If difference in heights is greater than 1, subtree is unbalanced
return False
return is_balanced_recursive(node.left) and is_balanced_recursive(node.right) # Recursively check left and right subtrees
return is_balanced_recursive(self.___) # Start recursion from root node
# Example usage:
bst = BST() # Create a new Binary Search Tree instance
bst.insert(50) # Insert some keys into the tree
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(10)
bst.insert(35)
bst.insert(45)
Ask AI
Ask anything or try one of the suggested questions to begin our chat
