Trees and Binary Search Trees

Introduction

Trees are one of the most important data structures in computer science. They model hierarchical relationships and enable efficient searching, sorting, and organization of data. Think of a tree as an organizational chart or a family tree - each person has a manager (parent) and may have subordinates (children).

In this lesson, we'll explore tree data structures, focusing on binary trees and binary search trees (BSTs). These structures form the foundation for many algorithms and real-world applications.

Tree Terminology

Before diving into implementation, let's understand the basic concepts:

Tree Components

        A (root)
       / \
      B   C
     / \   \
    D   E   F
       /
      G (leaf)

Root: The topmost node (A) with no parent
Parent: A node that has children (A is parent of B and C)
Child: A node that has a parent (B is child of A)
Leaf: A node with no children (D, E, F, G are leaves)
Internal Node: A node with at least one child (A, B, C, E)
Edge: The connection between two nodes
Path: Sequence of nodes from one node to another
Height: Length of longest path from root to leaf
Depth: Length of path from root to a specific node

Tree Properties

Height of tree above: 3 (longest path: A→B→E→G)
Depth of node G: 3
Degree of node B: 2 (two children)
Degree of node D: 0 (leaf node)

Binary Trees

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

Binary Tree Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Create a simple binary tree
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

Tree Traversal Algorithms

Tree traversal means visiting each node exactly once. There are three main methods:

1. Inorder Traversal (Left, Root, Right)

def inorder_traversal(node):
    """Left subtree → Root → Right subtree"""
    if node:
        inorder_traversal(node.left)
        print(node.value, end=" ")
        inorder_traversal(node.right)

# For our tree: 4 2 5 1 3

2. Preorder Traversal (Root, Left, Right)

def preorder_traversal(node):
    """Root → Left subtree → Right subtree"""
    if node:
        print(node.value, end=" ")
        preorder_traversal(node.left)
        preorder_traversal(node.right)

# For our tree: 1 2 4 5 3

3. Postorder Traversal (Left, Right, Root)

def postorder_traversal(node):
    """Left subtree → Right subtree → Root"""
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=" ")

# For our tree: 4 5 2 3 1

4. Level Order Traversal (Breadth-First)

from collections import deque

def level_order_traversal(root):
    """Visit nodes level by level"""
    if not root:
        return
    
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# For our tree: 1 2 3 4 5

Binary Search Trees (BSTs)

A Binary Search Tree is a binary tree with a special property: for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

BST Properties

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Left subtree of 8: {3, 1, 6, 4, 7} - all < 8
Right subtree of 8: {10, 14, 13} - all > 8
Same property holds for every subtree

BST Implementation

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        """Insert a value into the BST"""
        if not self.root:
            self.root = BSTNode(value)
            return
        
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = BSTNode(value)
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = BSTNode(value)
                    break
                current = current.right
    
    def search(self, value):
        """Search for a value in the BST"""
        current = self.root
        while current:
            if value == current.value:
                return True
            elif value < current.value:
                current = current.left
            else:
                current = current.right
        return False
    
    def inorder_traversal(self):
        """Return inorder traversal (sorted order)"""
        result = []
        self._inorder_helper(self.root, result)
        return result
    
    def _inorder_helper(self, node, result):
        if node:
            self._inorder_helper(node.left, result)
            result.append(node.value)
            self._inorder_helper(node.right, result)

# Usage
bst = BinarySearchTree()
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(value)

print("Inorder traversal:", bst.inorder_traversal())  # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print("Search for 6:", bst.search(6))  # True
print("Search for 9:", bst.search(9))  # False

BST Operations Analysis

Operation	Average Time	Worst Case
Insert	O(log n)	O(n)
Search	O(log n)	O(n)
Delete	O(log n)	O(n)
Inorder traversal	O(n)	O(n)

The worst case occurs when the tree becomes unbalanced (like a linked list).

Real-World Applications

File System Representation

class FileSystemNode:
    def __init__(self, name, is_file=False):
        self.name = name
        self.is_file = is_file
        self.children = {}  # For directories
        self.size = 0      # For files
    
    def add_child(self, child):
        if not self.is_file:
            self.children[child.name] = child
    
    def get_size(self):
        if self.is_file:
            return self.size
        return sum(child.get_size() for child in self.children.values())

# Building a file system tree
root = FileSystemNode("root")
home = FileSystemNode("home")
documents = FileSystemNode("documents")

root.add_child(home)
home.add_child(documents)

# Add some files
file1 = FileSystemNode("readme.txt", is_file=True)
file1.size = 1024
documents.add_child(file1)

print(f"Total size: {root.get_size()} bytes")

Expression Tree for Mathematical Expressions

class ExpressionNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
    
    def evaluate(self):
        if isinstance(self.value, (int, float)):
            return self.value
        
        left_val = self.left.evaluate() if self.left else 0
        right_val = self.right.evaluate() if self.right else 0
        
        if self.value == '+':
            return left_val + right_val
        elif self.value == '-':
            return left_val - right_val
        elif self.value == '*':
            return left_val * right_val
        elif self.value == '/':
            return left_val / right_val

# Build expression tree for (3 + 5) * 2
#       *
#      / \
#     +   2
#    / \
#   3   5

plus_node = ExpressionNode('+', ExpressionNode(3), ExpressionNode(5))
multiply_node = ExpressionNode('*', plus_node, ExpressionNode(2))

print(f"Result: {multiply_node.evaluate()}")  # 16

Decision Trees

class DecisionNode:
    def __init__(self, question, true_branch=None, false_branch=None, result=None):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch
        self.result = result
    
    def decide(self, features):
        if self.result is not None:
            return self.result
        
        if features.get(self.question, False):
            return self.true_branch.decide(features)
        else:
            return self.false_branch.decide(features)

# Simple decision tree for loan approval
# Is credit score > 700? -> Yes: approve, No: check income
high_credit = DecisionNode(result="Approved")
low_credit = DecisionNode(result="Denied")

decision_tree = DecisionNode("credit_score > 700", 
                           true_branch=high_credit, 
                           false_branch=low_credit)

applicant = {"credit_score > 700": True}
print(f"Decision: {decision_tree.decide(applicant)}")

Tree Balancing

One major issue with BSTs is that they can become unbalanced, leading to poor performance. In the next lesson on sorting and searching algorithms, we'll explore self-balancing trees like AVL trees and Red-Black trees.

Key Points to Remember

Trees represent hierarchical relationships with root, parent, and child nodes
Binary trees have at most two children per node
Tree traversal: inorder, preorder, postorder, and level-order
Binary Search Trees maintain ordered property for efficient searching
BST operations are O(log n) on average, but can degrade to O(n) when unbalanced
Trees are used in file systems, expression evaluation, decision making, and more

Trees provide hierarchical organization, but what about efficiently sorting and searching through data? In the next lesson, we'll explore fundamental sorting algorithms (bubble sort, quicksort, merge sort) and searching algorithms (binary search, linear search), understanding their performance characteristics and when to use each one.