Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Learn Challenge: Balanced Trees | Graphs
Algorithms and Data Structures Overview

book
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 returns False if 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

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?

How can we improve it?

Thanks for your feedback!

Section 4. Chapter 6
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)

Ask AI

expand
ChatGPT

Ask anything or try one of the suggested questions to begin our chat

some-alt