Trees Fundamentals: Hierarchical Data Structures

Introduction

If you thought about your family tree or an organizational chart, you’ve already encountered trees in the real world. In computer science, trees are hierarchical data structures that organize data in parent-child relationships—much like a family tree but with computational precision.

Trees are everywhere: file systems, XML/HTML documents, compiler abstract syntax trees, decision trees in machine learning, and binary search trees in databases. Understanding trees is fundamental to computer science.

This article explores tree fundamentals, types, and operations.

What Makes a Tree?

A tree is a connected acyclic graph. More practically:

Each node (except the root) has exactly one parent
Each node can have zero or more children
There’s exactly one path between any two nodes
The root is the single node without a parent

Key terminology:

Root: Topmost node
Leaf: Node with no children
Internal node: Node with at least one child
Height: Length of longest path from root to leaf
Depth: Length of path from root to node
Subtree: A node and all its descendants

Types of Trees

By number of children:

General trees: Unlimited children
Binary trees: Maximum 2 children per node
Ternary trees: Maximum 3 children per node

By properties:

Full binary tree: Every node has 0 or 2 children (no nodes with exactly 1 child)
Complete binary tree: All levels completely filled except possibly last, filled left to right
Perfect binary tree: All internal nodes have 2 children, all leaves at same level
Balanced tree: Left and right subtrees height difference is bounded (usually ≤ 1)
Binary Search Tree (BST): Left child < parent < right child

Binary Trees

The most common tree type in computer science. Each node has at most two children, typically called “left” and “right.”

Why binary trees matter:

Efficient search, insert, delete (O(log n) when balanced)
Represent hierarchical data naturally
Foundation for expression trees, syntax trees, decision trees

Tree Traversals

Processing every node in a tree requires systematic traversal. There are several fundamental approaches:

Depth-First Search (DFS):

Preorder: Visit node, then left subtree, then right (Root-Left-Right)
Inorder: Left subtree, node, right subtree (Left-Root-Right) — for BSTs gives sorted order
Postorder: Left subtree, right subtree, then node (Left-Right-Root)

Breadth-First Search (BFS):

Level order: Visit nodes level by level, left to right

# Inorder traversal (BST gives sorted order)
def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)

# Level order using queue
from collections import deque
def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Binary Search Trees (BST)

BSTs organize data for efficient lookup:

Left subtree contains only values less than node
Right subtree contains only values greater than node
Both subtrees are also BSTs

Operations:

Search: O(log n) average, O(n) worst if tree becomes skewed
Insert: Follow search path, add leaf
Delete: Three cases—leaf, one child, two children (replace with inorder successor)

Balancing Trees

When data insertions/deletions follow predictable patterns, BSTs can become unbalanced (essentially linked lists), losing their efficiency.

Self-balancing trees automatically maintain balance:

AVL trees: Height balance property (left and right heights differ by ≤ 1)
Red-black trees: Color-based balancing with simpler rotations
B-trees: Optimized for disk access

Applications of Trees

In computing:

File systems
HTML/XML DOM
Compilers (AST)
Routing tables (trie)

In algorithms:

Binary search
Heap structures
Decision trees (ML)
Graph traversal

In data organization:

Database indexes (B+ trees)
JSON structure
Organization charts

External Resources

Conclusion

Trees are fundamental to computer science, providing efficient data organization and manipulation. Understanding trees—particularly binary trees and BSTs—lays the foundation for more complex structures like heaps, tries, and balanced trees.

The key concepts—traversal, search, balance—apply broadly. Master these fundamentals, and you’ll be well-prepared for advanced data structures and algorithms.