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)
bst.insert(45)

Ask AI

expand
ChatGPT

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

some-alt