Trees

What Is a Tree?

A tree is a data structure that organises information into a branching, hierarchical shape rather than a straight line. Where an array or a linked list stores items one after another, a tree stores items in nodes that connect to multiple other nodes below them, the way a family tree branches from grandparents down to grandchildren, or the way folders on a computer contain other folders.

Every tree starts at a single node called the root. From the root, connections called edges lead down to child nodes, and each child can have children of its own. A node with children is a parent; a node with no children is a leaf. Any node reached by following edges downward from another node is a descendant, and the reverse relationship is an ancestor.

          root
         /    \
      child    child
      /   \        \
   leaf   leaf     leaf

Two more terms matter for describing a tree's shape. The depth of a node is how many edges separate it from the root (the root itself has depth 0). The height of the tree is the depth of its deepest leaf. A tree where every level is as full as possible before a new level starts is called balanced — balance turns out to matter a great deal for how fast a tree can be searched.

Binary Trees

The most common tree in introductory computing is the binary tree, where every node has at most two children, conventionally drawn as a left child and a right child. Restricting the branching to two makes binary trees simple to reason about and easy to search, which is why they show up constantly in exam specifications and real software alike.

Binary Search Trees

A binary search tree (BST) is a binary tree with one extra rule applied at every single node: everything in that node's left subtree is smaller than the node's own value, and everything in its right subtree is larger. Apply that rule consistently and the whole tree becomes searchable the same way a phone book is searchable — by repeatedly halving the space you still need to check.

Searching a balanced binary search tree for a value works like binary search on a sorted list: compare the target to the current node, go left if it is smaller, go right if it is larger, and stop when you find it or run out of tree. A balanced BST holding a million items needs at most about 20 comparisons to find any one of them, because each comparison eliminates roughly half of what remains — the same halving trick a phone book relies on, and the same reasoning covered in comparing algorithms.

That efficiency depends entirely on balance. If values are inserted in already-sorted order, a binary search tree can degrade into one long chain where every node has only a right child — at that point, searching it is no faster than walking a linked list from the head. Real-world database and language libraries use self-balancing variants (with names like AVL trees and red-black trees) specifically to guarantee the tree never collapses into a chain, but the balancing mechanics themselves are beyond what this lesson covers.

Visiting Every Node: Tree Traversal

Traversal means visiting every node in a tree exactly once, in some defined order. Because a tree branches instead of running in a straight line, there is more than one sensible order to do this in, and each has its own name and use.

Three traversal orders are built from the same three ingredients — visit the node itself, traverse its left subtree, traverse its right subtree — just rearranged, and they are usually described recursively:

• Pre-order (node, then left, then right) — visits a node before either of its children. Useful for copying a tree, since you create the parent before you need to attach children to it.
• In-order (left, then node, then right) — for a binary search tree specifically, this always produces the values in sorted, ascending order, because it fully explores everything smaller before visiting the node and everything larger afterward.
• Post-order (left, then right, then node) — visits a node only after both children are done. Useful for deleting a tree safely, since every child is cleared away before its parent, and for evaluating expression trees where an operator needs both operands calculated first.

A fourth approach, breadth-first traversal (also called level-order), ignores the recursive left/right pattern entirely and instead visits the tree level by level — the root first, then every node at depth 1 left to right, then every node at depth 2, and so on. It typically uses a queue to keep track of which node to visit next, in contrast to the other three orders, which naturally use the call stack through recursion.

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

Pre-order:   F B A D C E G I H
In-order:    A B C D E F G H I
Post-order:  A C E D B H I G F
Level-order: F B G A D I C E H

Where Trees Show Up

Trees are not just a diagram from a textbook. File systems model every folder and its contents as a tree, with the root directory at the top and files as leaves. The DOM that a web browser builds from an HTML page is a tree, with the html tag as the root and every nested tag a descendant. Decision trees in artificial intelligence branch on a series of yes/no questions to reach a classification. Databases commonly index their tables with a B-tree (a wider variant that allows more than two children per node) so that looking up a single row does not require scanning the entire table. Even the algorithm that suggests autocomplete words as you type often walks a specialised tree called a trie, built from shared prefixes.

Trees vs Linked Lists

Feature	Linked List	Tree
Shape	One straight chain	Branching, hierarchical
Pointers per node	One (or two, if doubly linked)	Two or more (children)
Searching a sorted structure	Must walk from the head, one node at a time	A balanced BST can skip past half the remaining nodes at each step
Natural fit for	Sequences, undo history, playlists	Folder structures, hierarchies, sorted lookups

Key Words

• Root — the single node at the top of a tree, with no parent
• Leaf — a node with no children
• Parent / child — a node with a connection, and the node one level below it
• Depth — the number of edges from a node back to the root
• Height — the depth of a tree's deepest leaf
• Binary tree — a tree where every node has at most two children
• Binary search tree — a binary tree where left subtrees hold smaller values and right subtrees hold larger ones
• Traversal — visiting every node in a tree exactly once, in a defined order