Binary Trees

🌲 What are Binary Trees?

Binary trees are specialized trees where each node has at most two children, typically called left and right child. They form the foundation for many advanced data structures and algorithms.


# Binary tree node structure
class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Create a simple binary tree
root = BinaryTreeNode(1)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)

2

Max Children

O(log n)

Balanced Height

3

Traversal Types

Binary Tree Properties

👥

Two Children Max

Each node has at most 2 children

Left child Right child

📏

Height Properties

Height affects performance

Balanced: O(log n) Skewed: O(n)

🔄

Recursive Structure

Each subtree is a binary tree

Left subtree Right subtree

🎯

Versatile

Foundation for many structures

BST Heaps

Lesson 1: Creating Binary Trees

Let's start by implementing a binary tree node and basic operations:

Binary Tree Example

Binary Tree Implementation


class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    def insert_left(self, data):
        """Insert a left child"""
        if self.left is None:
            self.left = BinaryTreeNode(data)
        else:
            new_node = BinaryTreeNode(data)
            new_node.left = self.left
            self.left = new_node
    
    def insert_right(self, data):
        """Insert a right child"""
        if self.right is None:
            self.right = BinaryTreeNode(data)
        else:
            new_node = BinaryTreeNode(data)
            new_node.right = self.right
            self.right = new_node
    
    def print_tree(self, level=0, prefix="Root: "):
        """Print the tree structure"""
        if self is not None:
            print(" " * (level * 4) + prefix + str(self.data))
            if self.left is not None or self.right is not None:
                if self.left:
                    self.left.print_tree(level + 1, "L--- ")
                else:
                    print(" " * ((level + 1) * 4) + "L--- None")
                if self.right:
                    self.right.print_tree(level + 1, "R--- ")
                else:
                    print(" " * ((level + 1) * 4) + "R--- None")

# Create the example tree
root = BinaryTreeNode(1)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)
root.left.left = BinaryTreeNode(4)
root.left.right = BinaryTreeNode(5)

print("Binary Tree Structure:")
root.print_tree()

Lesson 2: Binary Tree Traversals

There are three main ways to traverse a binary tree:

Binary Tree Traversals

🔹In-order Traversal (Left → Root → Right)


def inorder_traversal(root, result=[]):
    """In-order: Left → Root → Right"""
    if root:
        inorder_traversal(root.left, result)
        result.append(root.data)
        inorder_traversal(root.right, result)
    return result

# Example usage
result = []
inorder_traversal(root, result)
print("In-order:", result)  # [4, 2, 5, 1, 3]

🔹Pre-order Traversal (Root → Left → Right)


def preorder_traversal(root, result=[]):
    """Pre-order: Root → Left → Right"""
    if root:
        result.append(root.data)
        preorder_traversal(root.left, result)
        preorder_traversal(root.right, result)
    return result

# Example usage
result = []
preorder_traversal(root, result)
print("Pre-order:", result)  # [1, 2, 4, 5, 3]

🔹Post-order Traversal (Left → Right → Root)


def postorder_traversal(root, result=[]):
    """Post-order: Left → Right → Root"""
    if root:
        postorder_traversal(root.left, result)
        postorder_traversal(root.right, result)
        result.append(root.data)
    return result

# Example usage
result = []
postorder_traversal(root, result)
print("Post-order:", result)  # [4, 5, 2, 3, 1]

🔹Level-order Traversal (Breadth-First)


from collections import deque

def level_order_traversal(root):
    """Level-order: Visit level by level"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.data)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

# Example usage
result = level_order_traversal(root)
print("Level-order:", result)  # [1, 2, 3, 4, 5]

Lesson 3: Calculating Tree Properties

Let's implement functions to calculate important tree properties:

Tree Property Calculations

🔹Calculate tree height


def tree_height(root):
    """Calculate the height of the binary tree"""
    if not root:
        return -1  # Height of empty tree is -1
    
    left_height = tree_height(root.left)
    right_height = tree_height(root.right)
    
    return max(left_height, right_height) + 1

# Example usage
height = tree_height(root)
print(f"Tree height: {height}")  # Tree height: 2

🔹Count total nodes


def count_nodes(root):
    """Count total number of nodes"""
    if not root:
        return 0
    
    return 1 + count_nodes(root.left) + count_nodes(root.right)

# Example usage
total = count_nodes(root)
print(f"Total nodes: {total}")  # Total nodes: 5

🔹Count leaf nodes


def count_leaves(root):
    """Count leaf nodes (nodes with no children)"""
    if not root:
        return 0
    
    if not root.left and not root.right:
        return 1  # This is a leaf
    
    return count_leaves(root.left) + count_leaves(root.right)

# Example usage
leaves = count_leaves(root)
print(f"Leaf nodes: {leaves}")  # Leaf nodes: 3

🔹Check if tree is balanced


def is_balanced(root):
    """Check if the binary tree is height-balanced"""
    def check_balance(node):
        if not node:
            return 0, True  # height, is_balanced
        
        left_height, left_balanced = check_balance(node.left)
        right_height, right_balanced = check_balance(node.right)
        
        # Check if current node is balanced
        height_diff = abs(left_height - right_height)
        current_balanced = (height_diff <= 1 and 
                          left_balanced and right_balanced)
        
        current_height = max(left_height, right_height) + 1
        return current_height, current_balanced
    
    _, balanced = check_balance(root)
    return balanced

# Example usage
balanced = is_balanced(root)
print(f"Is balanced: {balanced}")  # Is balanced: True

🔹Find maximum value


def find_max(root):
    """Find the maximum value in the binary tree"""
    if not root:
        return float('-inf')
    
    max_val = root.data
    left_max = find_max(root.left)
    right_max = find_max(root.right)
    
    return max(max_val, left_max, right_max)

# Example usage
max_value = find_max(root)
print(f"Maximum value: {max_value}")  # Maximum value: 5

Lesson 4: Building Trees from Traversals

Learn how to construct binary trees from different traversal sequences:

Tree Construction

🔹Build tree from preorder and inorder


def build_tree_pre_in(preorder, inorder):
    """Build binary tree from preorder and inorder traversals"""
    if not preorder or not inorder:
        return None
    
    # First element in preorder is always root
    root_val = preorder[0]
    root = BinaryTreeNode(root_val)
    
    # Find root position in inorder
    root_idx = inorder.index(root_val)
    
    # Split inorder into left and right subtrees
    left_inorder = inorder[:root_idx]
    right_inorder = inorder[root_idx + 1:]
    
    # Split preorder accordingly
    left_preorder = preorder[1:1 + len(left_inorder)]
    right_preorder = preorder[1 + len(left_inorder):]
    
    # Recursively build subtrees
    root.left = build_tree_pre_in(left_preorder, left_inorder)
    root.right = build_tree_pre_in(right_preorder, right_inorder)
    
    return root

# Example usage
preorder = [1, 2, 4, 5, 3]
inorder = [4, 2, 5, 1, 3]
reconstructed_tree = build_tree_pre_in(preorder, inorder)

print("Reconstructed tree:")
reconstructed_tree.print_tree()

🔹Build complete binary tree from array


def build_tree_from_array(arr, index=0):
    """Build complete binary tree from array representation"""
    if index >= len(arr) or arr[index] is None:
        return None
    
    root = BinaryTreeNode(arr[index])
    root.left = build_tree_from_array(arr, 2 * index + 1)
    root.right = build_tree_from_array(arr, 2 * index + 2)
    
    return root

# Example usage - array representation of complete binary tree
# Index:  0  1  2  3  4  5  6
# Array: [1, 2, 3, 4, 5, 6, 7]
#        1
#       / \
#      2   3
#     / \ / \
#    4 5 6  7

tree_array = [1, 2, 3, 4, 5, 6, 7]
array_tree = build_tree_from_array(tree_array)

print("Tree from array:")
array_tree.print_tree()

Types of Binary Trees

Full Binary Tree

Every node has 0 or 2 children
No node has exactly 1 child
Also called proper binary tree
Efficient memory usage

Complete Binary Tree

All levels filled except possibly last
Last level filled left to right
Used in heap data structure
Array representation efficient

Perfect Binary Tree

All internal nodes have 2 children
All leaves at same level
Height h has 2^(h+1) - 1 nodes
Perfectly balanced

Balanced Binary Tree

Height difference ≤ 1 for all nodes
Ensures O(log n) operations
AVL and Red-Black trees
Self-balancing variants

Practice Project: Expression Tree

Let's build an expression tree to evaluate mathematical expressions:

Expression Tree Implementation


class ExpressionTree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    def is_operator(self, char):
        """Check if character is an operator"""
        return char in ['+', '-', '*', '/', '^']
    
    def evaluate(self):
        """Evaluate the expression tree"""
        # If it's a number (leaf node)
        if not self.is_operator(self.data):
            return float(self.data)
        
        # If it's an operator, evaluate left and right subtrees
        left_val = self.left.evaluate()
        right_val = self.right.evaluate()
        
        # Apply the operator
        if self.data == '+':
            return left_val + right_val
        elif self.data == '-':
            return left_val - right_val
        elif self.data == '*':
            return left_val * right_val
        elif self.data == '/':
            return left_val / right_val
        elif self.data == '^':
            return left_val ** right_val
    
    def to_infix(self):
        """Convert expression tree to infix notation"""
        if not self.is_operator(self.data):
            return str(self.data)
        
        left_expr = self.left.to_infix()
        right_expr = self.right.to_infix()
        
        return f"({left_expr} {self.data} {right_expr})"
    
    def to_prefix(self):
        """Convert expression tree to prefix notation"""
        if not self.is_operator(self.data):
            return str(self.data)
        
        left_expr = self.left.to_prefix()
        right_expr = self.right.to_prefix()
        
        return f"{self.data} {left_expr} {right_expr}"
    
    def to_postfix(self):
        """Convert expression tree to postfix notation"""
        if not self.is_operator(self.data):
            return str(self.data)
        
        left_expr = self.left.to_postfix()
        right_expr = self.right.to_postfix()
        
        return f"{left_expr} {right_expr} {self.data}"

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

root = ExpressionTree('*')
root.left = ExpressionTree('+')
root.right = ExpressionTree('-')

root.left.left = ExpressionTree('3')
root.left.right = ExpressionTree('4')
root.right.left = ExpressionTree('5')
root.right.right = ExpressionTree('2')

# Test the expression tree
print("Expression Tree Operations:")
print("=" * 40)
print(f"Infix:   {root.to_infix()}")      # ((3 + 4) * (5 - 2))
print(f"Prefix:  {root.to_prefix()}")     # * + 3 4 - 5 2
print(f"Postfix: {root.to_postfix()}")    # 3 4 + 5 2 - *
print(f"Result:  {root.evaluate()}")      # 21.0

# Build another expression: 2 ^ (3 + 1)
expr2 = ExpressionTree('^')
expr2.left = ExpressionTree('2')
expr2.right = ExpressionTree('+')
expr2.right.left = ExpressionTree('3')
expr2.right.right = ExpressionTree('1')

print(f"\nSecond expression: {expr2.to_infix()}")  # (2 ^ (3 + 1))
print(f"Result: {expr2.evaluate()}")               # 16.0