liveBook · Manning

Tree

As explained in Algorithms Every Programmer Should Know

A tree is a hierarchical data structure in which every node descends from a single root and edges flow downward without loops.

A tree organizes data hierarchically, like a file system or corporate org chart. It has one root; every other node descends from it, with edges flowing downward and no loops. Nodes without children are leaves. section 1.4.4 section 1.5

Structural constraints define common tree types:

  • A binary tree gives each node at most two children. section 1.4.4
  • A full binary tree gives each node either zero or two children. section 1.4.4
  • A perfect binary tree has leaves at the same depth. section 1.4.4

To visit nodes, breadth-first search (BFS) explores level by level using a FIFO queue; depth-first search (DFS) follows a branch before backtracking, using a LIFO stack. Both take O(V) time; BFS space depends on tree width, while DFS space depends on depth. section 1.5 section 1.4.4

Figure 1.8 A comparison of common binary tree structural variations. Left: A standard binary tree where nodes have a maximum of two children. Middle: A full binary tree enforcing that nodes possess either exactly zero or exactly two child nodes. Right: A highly uniform perfect binary tree where all interior nodes contain two children and every leaf node aligns at the exact same depth level.

Compare binary, full, and perfect tree shapes. section 1.4.4

Figure 1.9 The two fundamental strategies for searching non-linear data structures. Left: Depth-First Search (DFS) goes deep down a single path to a leaf node. Right: Breadt-First Search (BFS) expands outward, exploring all the neighboring nodes layer by layer before descending to the next level.

See how depth-first and breadth-first search explore a tree differently. section 1.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines tree variants and explains traversal strategies and space bounds, without detailing search algorithms.
Examples
Uses a corporate org chart and file system analogy, plus diagrams of tree types and search strategies.
What it assumes
Builds from linear data structures and relates traversal to stacks and queues without specifying outside prerequisites.
What you can do after
Apply breadth-first or depth-first traversal using a queue or stack, respectively.
How it connects
Connects trees with graphs, binary trees, breadth-first search, depth-first search, stacks, and queues.

Also explained in

Compare how 14 books explain tree →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.