Lecture 174:- Trees Class - 4 

Certainly, let's explore another aspect of a tree class. In this example, we'll implement a Binary Tree class with methods to find the lowest common ancestor (LCA) of two nodes and to check if the tree is balanced.

pythonCopy code

class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None class BinaryTree: def __init__(self, root_data): self.root = TreeNode(root_data) def find_lca(self, node1, node2): return self._find_lca_recursive(self.root, node1, node2) def _find_lca_recursive(self, current_node, node1, node2): if current_node is None: return None if current_node.data == node1 or current_node.data == node2: return current_node left_lca = self._find_lca_recursive(current_node.left, node1, node2) right_lca = self._find_lca_recursive(current_node.right, node1, node2) if left_lca and right_lca: return current_node return left_lca if left_lca else right_lca def is_balanced(self): return self._is_balanced_recursive(self.root) is not None def _is_balanced_recursive(self, node): if node is None: return 0 left_height = self._is_balanced_recursive(node.left) right_height = self._is_balanced_recursive(node.right) if left_height is None or right_height is None: return None if abs(left_height - right_height) > 1: return None return max(left_height, right_height) + 1 # Example usage tree = BinaryTree(20) tree.root.left = TreeNode(10) tree.root.right = TreeNode(30) tree.root.left.left = TreeNode(5) tree.root.left.right = TreeNode(15) tree.root.right.left = TreeNode(25) tree.root.right.right = TreeNode(35) lca_node = tree.find_lca(5, 15) print("Lowest Common Ancestor of 5 and 15:", lca_node.data) print("Is the tree balanced?", tree.is_balanced())

In this example, we've added two new methods to the BinaryTree class: find_lca and is_balanced.

The find_lca method finds the lowest common ancestor of two nodes in the binary tree. It does this by recursively traversing the tree and checking if the current node is one of the nodes we are looking for. If one node is found in the left subtree and the other in the right subtree, the current node is the lowest common ancestor.

The is_balanced method checks if the binary tree is balanced. A balanced tree is defined as a tree in which the heights of the left and right subtrees of every node differ by at most one. This method uses a recursive approach to calculate the heights of subtrees and checks if the tree is balanced accordingly.

This example demonstrates the implementation of finding the lowest common ancestor and checking the balance of a binary tree. Trees can be used for a wide range of applications, and understanding these fundamental operations is essential when working with tree-based data structures.