Lecture 176:-FW To Find Height Balanced Tree

To find a height-balanced binary tree, you can implement a function that checks whether a given binary tree is height-balanced or not. A height-balanced binary tree is a tree in which the heights of the left and right subtrees of every node differ by at most one.

Here's a Python implementation to determine if a binary tree is height-balanced:

pythonCopy code

class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def is_height_balanced(root): if root is None: return True left_height = height_of_binary_tree(root.left) right_height = height_of_binary_tree(root.right) if abs(left_height - right_height) > 1: return False return is_height_balanced(root.left) and is_height_balanced(root.right) def height_of_binary_tree(node): if node is None: return 0 left_height = height_of_binary_tree(node.left) right_height = height_of_binary_tree(node.right) return max(left_height, right_height) + 1 # Example usage root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) balanced = is_height_balanced(root) if balanced: print("The binary tree is height-balanced.") else: print("The binary tree is not height-balanced.")

In this example, the TreeNode class is defined to represent nodes of the binary tree. The is_height_balanced function checks whether a given binary tree is height-balanced or not. It recursively calculates the height of the left and right subtrees using the height_of_binary_tree function and compares their heights to determine if the current node's subtree is balanced.

The height_of_binary_tree function calculates the height of a binary tree using a similar recursive approach as before.

Keep in mind that this implementation has a time complexity of O(N^2), where N is the number of nodes in the binary tree, due to repeated calculations of heights. This can be optimized to O(N) using a bottom-up approach to calculate heights while simultaneously checking for balance.