Skip to main content
Be Bitwise

Trees & Hierarchical Data

Arrays, Lists & Data Structures · Coding Fundamentals track

8 min read

In this module

Hierarchical Data

Not every collection of data fits neatly into a line. File systems contain directories inside directories. HTML documents nest elements inside other elements. Organisation charts stack managers above managers. Data with this shape is hierarchical, and the natural way to represent it is a tree.

A tree is a collection of nodes connected by edges, with these properties:

  • One special node called the root sits at the top.
  • Every other node has exactly one parent.
  • A node can have zero or more children.
  • A childless node is a leaf.

Binary Trees

A binary tree caps each node at two children, called the left child and the right child. Binary trees are the most studied — and most generally useful — kind of tree in computer science.

Each node in a binary tree is just a struct with three fields: a value, a pointer to the left child (or null), and a pointer to the right child (or null).

Key Concept

A tree is a hierarchical data structure with a root node and parent-child relationships. A binary tree restricts each node to at most two children. Trees naturally represent hierarchical data and enable efficient searching, sorting, and hierarchical processing.

Binary Search Trees

A binary search tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

This ordering lets you search efficiently. To find the value 6:

  1. Start at root (8). 6 < 8, go left.
  2. At node 3. 6 > 3, go right.
  3. At node 6. Found it.

Every comparison cuts the remaining tree roughly in half. In a balanced BST with n nodes, search takes O(log n) time — same as binary search on a sorted array.

Tree Traversal

Visiting every node in a tree is called traversal. There are three classic orders for binary trees:

In-order (left, root, right): Visits nodes in sorted order for a BST.

text
In-order of the tree above: 1, 3, 6, 8, 10, 14

Pre-order (root, left, right): Useful for copying or serialising a tree.

text
Pre-order: 8, 3, 1, 6, 10, 14

Post-order (left, right, root): Useful for deleting a tree or evaluating expressions.

text
Post-order: 1, 6, 3, 14, 10, 8

All three traversals fall out of recursion:

text
function in_order(node) {
if node == null { return }
in_order(node.left)
print(node.value)
in_order(node.right)
}

This is recursion at its happiest. The shape of the algorithm mirrors the shape of the data.

The explorer below starts with the same tree. Pick an order and step through it, keeping an eye on the call stack, then press Insert 1 to 7 sorted and watch the height climb to 7 when 3 levels would do. Switch to Search to replay the hunt for 6 one comparison at a time.

Binary search tree explorer

Pick a traversal and step through it, or switch to search. Insert values to reshape the tree.

Mode
13681014
CurrentVisitedOn the call stack6 nodes, height 3 (minimum 3 = ⌈log₂(6+1)⌉)

In-order: left subtree, node, right subtree.

Visit order

Here's the same idea in C, with each node a struct holding a value and two child pointers. The program builds the tree above, then builds a second one from the same values fed in sorted order. Predict both heights before you run it.

Try itMove the in-order print to before or after the recursive calls to get pre-order or post-order.
C (GCC 9.2.0)

Both trees hold the same values and print the same in-order sequence, but tree b is the degenerate case from the next section: a linked list in disguise.

Balanced vs. Unbalanced Trees

A BST is only efficient when it stays roughly balanced, with left and right subtrees at each node coming out at roughly the same height. In the worst case, a BST collapses into a straight line — basically a linked list — and search degrades to O(n).

Balanced (height 3):

Degenerate (height 5):

Height here counts the number of levels (nodes in the longest root-to-leaf path). Some references define height as the number of edges instead, which gives a number one smaller.

Self-balancing trees like AVL trees and red-black trees restructure themselves after insertions and deletions to keep their O(log n) height. Most standard library implementations of ordered sets and maps lean on red-black trees under the hood.

Trees in the Real World

Trees are everywhere in computing:

  • File systems are trees: directories contain files and subdirectories.
  • The DOM (Document Object Model) in browsers is a tree of HTML elements.
  • Compilers build abstract syntax trees (ASTs) to capture the shape of your code before lowering it to machine instructions.
  • Decision trees drive classification in machine learning.
  • B-trees keep databases and file systems efficient when storing and retrieving data on disk.

Run into hierarchical or recursive data in the wild and trees are almost always the right data structure. Internalising them sets you up for algorithms, compilers, databases, and systems programming.

Trees and Recursion

Trees have an unusually tight bond with recursion. A tree is itself a recursive structure: every subtree is a tree. So most tree algorithms come out naturally recursive — process the root, then recurse into each subtree. Traversal, searching, insertion, deletion, and balancing all follow that pattern. If recursion still feels slippery, trees are where it tends to click. The shape of the data and the shape of the algorithm that processes it line up perfectly, which is when the recursive approach starts feeling inevitable rather than clever. The connection between recursive data structures and recursive algorithms is one of computer science's most rewarding insights.