Course Content
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
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
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.
Everything was clear?
Course Content
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
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
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.
Everything was clear?
