Python - Data Structures - Trees

Data Structures - Trees in Python

Trees are one of the most important non-linear data structures in computer science. A tree structure is hierarchical, consisting of nodes with a parent-child relationship. It is widely used in scenarios such as hierarchical data representation, file systems, databases, decision-making processes, parsers, and more.

In this document, we will explore tree data structures in depth, including terminology, types of trees, common tree operations, traversals, binary trees, binary search trees, implementation using Python, and real-world applications.

Basic Terminology

• Node: The fundamental part of a tree containing data.
• Root: The top-most node of the tree.
• Child: Node descended from another node.
• Parent: A node with children.
• Leaf: A node with no children.
• Edge: Connection between one node and another.
• Height: The longest path from root to a leaf.
• Depth: The number of edges from root to that node.

Types of Trees

• Binary Tree
• Binary Search Tree
• AVL Tree
• Red-Black Tree
• Trie
• Heap
• B-Tree

Binary Tree

A binary tree is a tree where each node has at most two children referred to as the left child and the right child.

Node Structure

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.data = key

Creating a Simple Tree

def build_tree():
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    return root

Tree Traversal Techniques

Inorder Traversal (Left, Root, Right)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

Preorder Traversal (Root, Left, Right)

def preorder(root):
    if root:
        print(root.data, end=" ")
        preorder(root.left)
        preorder(root.right)

Postorder Traversal (Left, Right, Root)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=" ")

Level Order Traversal (Breadth-First Search)

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Binary Search Tree (BST)

A Binary Search Tree is a type of binary tree where nodes are arranged in order. For each node:

• Left subtree has nodes less than the node’s key
• Right subtree has nodes greater than the node’s key

Inserting a Node in BST

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.data:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

Searching in BST

def search(root, key):
    if root is None or root.data == key:
        return root
    if key < root.data:
        return search(root.left, key)
    return search(root.right, key)

Deleting a Node from BST

def find_min(node):
    while node.left:
        node = node.left
    return node

def delete_node(root, key):
    if not root:
        return root
    if key < root.data:
        root.left = delete_node(root.left, key)
    elif key > root.data:
        root.right = delete_node(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        temp = find_min(root.right)
        root.data = temp.data
        root.right = delete_node(root.right, temp.data)
    return root

Height and Depth of Tree

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

Counting Nodes, Leaves, Internal Nodes

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def count_leaves(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

def count_internal_nodes(root):
    if not root or (not root.left and not root.right):
        return 0
    return 1 + count_internal_nodes(root.left) + count_internal_nodes(root.right)

Balanced Binary Tree

A tree is height-balanced if for every node, the difference in height of the left and right subtree is at most 1.

def is_balanced(root):
    def check(node):
        if not node:
            return 0, True
        left_height, left_balanced = check(node.left)
        right_height, right_balanced = check(node.right)
        balanced = (left_balanced and right_balanced and abs(left_height - right_height) <= 1)
        return max(left_height, right_height) + 1, balanced

    return check(root)[1]

Lowest Common Ancestor (LCA)

def lca(root, n1, n2):
    if not root:
        return None
    if root.data > max(n1, n2):
        return lca(root.left, n1, n2)
    elif root.data < min(n1, n2):
        return lca(root.right, n1, n2)
    else:
        return root

Invert a Binary Tree (Mirror)

def invert_tree(root):
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

Tree Representations

• Linked Representation (Using Nodes and Pointers)
• Array Representation (Used in Heaps)

Heap (Binary Heap)

A binary heap is a complete binary tree where each node is greater (max-heap) or smaller (min-heap) than its children.

Min-Heap Example with heapq

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heapq.heappop(heap))  # 1

Tree Applications

• Hierarchical data representation
• Syntax trees in compilers
• File system structures
• Binary search trees for fast lookup
• Heaps for priority queues
• Tries for dictionary and autocomplete

Summary of Tree Traversals

• Inorder: Left → Root → Right
• Preorder: Root → Left → Right
• Postorder: Left → Right → Root
• Level Order: Breadth-First Search

Tree Interview Problems

• Maximum Depth of Tree
• Diameter of Tree
• Path Sum
• Serialize and Deserialize Binary Tree
• Construct Tree from Preorder and Inorder Traversals

Diameter of Binary Tree

def diameter(root):
    res = [0]
    def depth(node):
        if not node:
            return 0
        L = depth(node.left)
        R = depth(node.right)
        res[0] = max(res[0], L + R)
        return 1 + max(L, R)
    depth(root)
    return res[0]

Trees are a foundational data structure in computer science that enable efficient storage, access, and manipulation of hierarchical data. From simple binary trees to more complex trees like AVL, heaps, and tries, trees offer a wide range of applications across domains.

In Python, trees are most commonly implemented using classes and recursion. Mastering trees allows you to solve complex problems in algorithms, system design, data storage, and parsing. Understanding traversals, insertions, deletions, and structural properties like balance and height is crucial for building efficient tree-based solutions.

Whether you are preparing for interviews or building complex software systems, a solid understanding of trees will help you organize and manage data effectively.