Data Structures - Trees

Understanding the Structure of a Tree

Every tree starts with a root — the topmost node from which all other nodes grow. From the root, data branches out through connections called edges, forming parent-child relationships. Each node can have zero, one, or multiple children, depending on the tree type.

This structure creates a clear hierarchy. The top node is the root. The bottom nodes, with no children, are called leaves. Nodes in between act as connectors, called internal nodes. These relationships define how data is linked and traversed.

            A
           / \
          B   C
         / \
        D   E
        

This hierarchical arrangement allows trees to represent data that naturally forms layers. It’s the same model used in file systems, website sitemaps, and XML or JSON documents. Each branch represents a logical path leading to smaller subsets of data.

Key Tree Terminologies

• Node: The fundamental unit of a tree that stores data.
• Root: The first or topmost node of a tree.
• Parent and Child: A node with children is a parent; the nodes beneath it are its children.
• Leaf: A node with no children — it represents the end of a path.
• Edge: The connection or link between two nodes.
• Subtree: A smaller tree structure that branches from a parent node.
• Height and Depth: The longest path from the root to a leaf defines height; depth is the distance from the root to a specific node.
• Degree: The number of children a node has.

Representing a Tree in Code

Trees are best represented using classes or objects. Each node typically stores its value and references to its child nodes. Here’s a basic example in Python that captures a simple tree structure:

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []  # allows multiple children

# Example: Building a tree
root = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")

root.children.extend([b, c])
b.children.extend([d, e])
    

This code represents the same tree diagram shown earlier. The children list lets each node connect to multiple nodes, creating a hierarchical structure where relationships are easily traceable.

Types of Trees in Data Structures

Not all trees are structured the same way. Depending on how many children a node can have or how the nodes are connected, trees can take different forms. Each type is designed for specific operations, balancing efficiency and complexity in different ways.

Understanding these variations helps you choose the right structure for your application — whether it’s for managing hierarchical data, improving search performance, or implementing algorithms in databases and AI systems.

1. General Tree

A General Tree is the most flexible type of tree where each node can have any number of children. There’s no fixed limit on branching, which makes it ideal for representing real-world hierarchies.

        A
      / | \
     B  C  D
       / \
      E   F
    

In this example, node A has three children (B, C, and D), and node C further expands into E and F. This flexibility makes general trees ideal for representing structures such as:

• File systems with folders and subfolders
• Organisational hierarchies
• XML or HTML document object models

2. Binary Tree

A Binary Tree is one of the most common types of trees. Each node can have at most two children — a left and a right child. This restriction makes binary trees easier to implement and analyse.

        A
       / \
      B   C
     / \
    D   E
    

• Each node has zero, one, or two children.
• Left and right subtrees are distinct and ordered.
• The topmost node is called the root.

Binary trees are the foundation of many advanced data structures such as Binary Search Trees (BSTs), Heaps, and AVL Trees. Each of these builds upon the same structure but applies additional rules for efficiency.

3. Types of Binary Trees

Binary trees can take different shapes depending on how completely their levels are filled or how nodes are distributed. Here are the main types you’ll encounter:

a. Full Binary Tree

Every node has either 0 or 2 children — there are no nodes with only one child.

        A
       / \
      B   C
     / \   \
    D   E   F
    

This structure ensures balance in the branching logic, commonly used in expression parsing and logical computations.

b. Complete Binary Tree

All levels of the tree are completely filled except possibly the last one, which must be filled from left to right.

        A
       / \
      B   C
     / \  /
    D  E F
    

Complete binary trees are the backbone of Heaps and Priority Queues, ensuring efficient storage and predictable performance.

c. Perfect Binary Tree

In a Perfect Binary Tree, all internal nodes have two children, and all leaf nodes exist on the same level.

        A
       / \
      B   C
     / \ / \
    D  E F  G
    

This structure is both full and complete, meaning it’s perfectly balanced and ideal for representing data with equal depth, such as tournament brackets or balanced search trees.

4. Balanced and Special Trees (For Awareness)

In real-world systems, trees often need to stay balanced to maintain performance. Variants like AVL Trees and Red-Black Trees automatically adjust themselves to keep operations efficient. You’ll explore these in later lessons, but for now, remember that balance prevents a tree from degrading into a linear list.

Other specialised trees include:

• Expression Trees – Used by compilers to evaluate arithmetic expressions.
• Decision Trees – Applied in AI and machine learning for classification problems.
• Heap Trees – Manage priority-based data in sorting algorithms.
• B-Trees – Used in databases and file systems for efficient indexing.

Tree Traversal: Visiting Every Node with Purpose

Building a tree is only half the story. The real power of trees lies in how you can traverse them—visiting each node to read, process, or modify data in a defined order. Traversal determines how your program interprets the structure, whether it’s printing values, searching for an item, or calculating relationships between nodes.

Because trees are non-linear, you can’t simply move left to right as in an array. You need strategies that decide which node to visit first, and how to move through branches efficiently. These strategies fall under two main categories: Depth-First Traversal (DFS) and Breadth-First Traversal (BFS).

Depth-First Traversal (DFS)

Depth-First Traversal explores as far down a branch as possible before backtracking. It’s like exploring every hallway in a building before moving to the next one. DFS is typically implemented using recursion or a stack.

DFS has three primary variations that differ in the order of visiting the Root, Left, and Right nodes:

1. Preorder Traversal (Root → Left → Right)

You visit the root node first, then traverse the left subtree, followed by the right subtree. Preorder is useful when you want to create a copy of the tree or print its structure.

        A
       / \
      B   C
     / \
    D   E
    

Preorder Output: A → B → D → E → C

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)
    

2. Inorder Traversal (Left → Root → Right)

You start from the leftmost node, then visit the root, and finally move to the right. In Binary Search Trees, this traversal always produces the values in sorted order.

Inorder Output: D → B → E → A → C

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)
    

3. Postorder Traversal (Left → Right → Root)

You visit the left subtree first, then the right, and finally the root node. This order is commonly used when deleting nodes or evaluating expression trees because it ensures child nodes are processed before their parents.

Postorder Output: D → E → B → C → A

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")
    

Breadth-First Traversal (BFS)

Breadth-First Traversal, also known as Level Order Traversal, visits nodes level by level from top to bottom. It explores all nodes at one depth before moving to the next. BFS is commonly implemented using a queue data structure.

        A
       / \
      B   C
     / \
    D   E
    

Level Order Output: A → B → C → D → E

from collections import deque

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

Complete Example

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

# Build the tree
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

# Traversals
print("Preorder Traversal:")
preorder(root)

print("\nInorder Traversal:")
inorder(root)

print("\nPostorder Traversal:")
postorder(root)

print("\nLevel Order Traversal:")
level_order(root)
    

Expected Output:

Preorder Traversal:  A B D E C
Inorder Traversal:   D B E A C
Postorder Traversal: D E B C A
Level Order:         A B C D E
    

Binary Search Trees (BST): Organising Data for Faster Access

A Binary Search Tree (BST) is a special type of binary tree that follows a simple but powerful rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This ordering allows fast searching, insertion, and deletion — operations that take time proportional to the tree’s height.

BSTs form the foundation of many modern systems such as databases, compilers, and file indexes. When balanced properly, they can perform searches in O(log n) time, which is significantly faster than linear structures like arrays or linked lists.

Structure and Property of BST

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

In this example:

• All values in the left subtree of 8 (3, 1, 6, 4, 7) are smaller than 8.
• All values in the right subtree of 8 (10, 14, 13) are larger than 8.
• Each subtree also follows the same rule recursively.

This structure ensures that data is always stored in a sorted and searchable form, making BSTs ideal for ordered datasets and fast lookup operations.

Key Operations on a BST

1. Searching

To search for a value, start from the root and compare the target value with the current node. If it’s smaller, move left; if larger, move right. Repeat until the value is found or a null node is reached.

def search(node, key):
    if node is None or node.value == key:
        return node
    if key < node.value:
        return search(node.left, key)
    else:
        return search(node.right, key)
    

For example, searching for 7 in the above tree follows this path: 8 → 3 → 6 → 7. The value is found after just a few comparisons.

2. Insertion

Inserting a new value follows the same logic as searching. Traverse the tree until you find the correct empty spot (either a left or right child) and place the new node there.

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.value:
        node.left = insert(node.left, key)
    elif key > node.value:
        node.right = insert(node.right, key)
    return node
    

Example: inserting 5 into the BST will place it as the left child of 6.

        8
       / \
      3   10
     / \    
    1   6
       / 
      5
    

3. Deletion

Deleting a node is slightly more complex because it depends on how many children the node has:

• Case 1: The node has no children (a leaf) — remove it directly.
• Case 2: The node has one child — replace it with its child.
• Case 3: The node has two children — replace it with its inorder successor (the smallest node in the right subtree).

The deletion logic ensures that the BST property remains intact after removing a node.

Traversal in BST

Traversal defines how nodes are visited and read. Among all traversal types, Inorder Traversal is particularly important for BSTs because it always produces data in ascending order.

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

Time Complexity

Applications of Binary Search Trees

• Databases: Efficient record lookup and indexing.
• Compilers: Symbol tables for variable tracking.
• File Systems: Directory management and search.
• Search Engines: Word indexing and retrieval systems.
• AI and Games: Decision trees for logic and pathfinding.

Key Takeaways and Practical Insights

Trees bring order to complexity. They allow you to organise, search, and process data in ways that linear structures simply can’t. Whether you’re mapping file directories, building search features, or managing hierarchical relationships, trees provide the foundation for efficiency and scalability.

What makes them powerful is their adaptability — from simple general trees that handle unlimited branching to binary trees that bring balance and precision, and binary search trees (BSTs) that make searching and sorting lightning fast.

Common Mistakes to Avoid

• Forgetting that each tree has only one root.
• Confusing depth with height — depth measures from the root down; height measures from a node to its deepest leaf.
• Not balancing a BST — unbalanced trees can degrade into linked lists and lose efficiency.
• Using the wrong traversal method — preorder for structure copying, inorder for sorting, and postorder for deletion.

Real-World Applications

Trees are everywhere — from databases and compilers to AI and web browsers. Here’s where you encounter them daily:

• File Systems: Folders, subfolders, and files form a hierarchical structure.
• HTML DOM: Web pages use a tree to connect elements and attributes.
• Machine Learning: Decision trees power classification and regression models.
• Game Development: Trees represent decision logic and object hierarchies.
• Databases: B-Trees and AVL Trees speed up indexing and query performance.