What a Tree Is

Q: What makes a tree a tree, rather than just any connected structure?

Every node has exactly one parent (except the root), with no cycles

You've already met trees, even if nobody called them that. A folder full of folders. An org chart. The nested tags of an HTML page. All of them share one shape: one thing at the top, branching down into more things, which branch into more things, until the branching stops.

The mental model: one parent, any number of children

What it actually is. A tree is made of nodes, connected so that every node has exactly one parent (except the very top one) and any number of children. That "exactly one parent" rule is what makes it a tree and not just any tangle of connections - there's no way to loop back around to somewhere you already were.

flowchart TD
  Root["project (root)"] --> Src["src"]
  Root --> Tests["tests"]
  Root --> Readme["README.md (leaf)"]
  Src --> Main["main.py (leaf)"]
  Src --> Utils["utils.py (leaf)"]
  Tests --> TestMain["test_main.py (leaf)"]

📝 Terminology.

The root is the single node at the top with no parent - project above.
A node's children are the nodes directly below it that it points to.
A leaf is a node with no children - the branching stops there (README.md, main.py, and the rest).
The height of a tree is the number of steps from the root down to its deepest leaf.

class Folder:
    def __init__(self, name, children=None):
        self.name = name
        self.children = children or []

root = Folder("project", [
    Folder("src", [Folder("main.py"), Folder("utils.py")]),
    Folder("tests", [Folder("test_main.py")]),
    Folder("README.md"),
])

def is_leaf(node):
    return len(node.children) == 0

def count_leaves(node):
    if is_leaf(node):
        return 1
    return sum(count_leaves(child) for child in node.children)

def height(node):
    if is_leaf(node):
        return 0
    return 1 + max(height(child) for child in node.children)

print(count_leaves(root))
print(height(root))

4
2

What just happened: count_leaves and height both walk the tree the same way every tree-walking function does - check the current node, then recurse into each child and combine the results. This is the same "self-similar problem" shape from Recursion, Finally: a folder containing folders is a smaller version of the same problem, all the way down to a leaf.

Why trees show up everywhere

File systems. Folders contain folders and files; a file is a leaf, a folder with contents is an internal node, the drive's top level is the root.

Org charts. A manager has reports, who may have their own reports; an individual contributor with no reports is a leaf.

The DOM (a web page). <body> contains <div>s, which contain more elements, down to leaf elements like <img> or text nodes. Every time you've called document.querySelector and it "found the right element," something walked this tree for you.

Any "this contains smaller versions of itself" data. Nested comments, a company's category hierarchy, a decision tree - if the shape is "one thing branching into more things, with no cycles," it's a tree.

💡 Key point. A linked list (see Data Structures, Explained) is actually a special, restricted case of a tree - one where every node has at most one child. A tree just lets a node branch into more than one.

Recap

A tree is nodes connected so every node has exactly one parent (except the root) and any number of children.
The root has no parent; a leaf has no children; height is the longest path from root to leaf.
File systems, org charts, and the DOM are all trees - the shape shows up constantly once you recognize it.
Tree-walking code is naturally recursive: handle one node, recurse into its children, combine the results.

Next: one specific rule turns a tree into a structure you can search almost as fast as binary search.

[
  {
    "q": "What makes a tree a tree, rather than just any connected structure?",
    "choices": ["Every node has exactly one parent (except the root), with no cycles", "Every node must have exactly two children", "All nodes must hold numbers", "It must be sorted"],
    "answer": 0,
    "explain": "The one-parent, no-cycles rule is what defines the branching tree shape - a binary tree (max two children per node) is one specific kind of tree, not the definition of 'tree' itself."
  },
  {
    "q": "What is a leaf?",
    "choices": ["The root node", "A node with no children", "Any node with exactly one child", "The deepest node in the tree, always"],
    "answer": 1,
    "explain": "A leaf is where the branching stops - it has no children, though it isn't necessarily the single deepest node if the tree is unbalanced."
  }
]

← Guide overview · Phase 2: Binary Search Trees →

Check your understanding 2 questions

1. What makes a tree a tree, rather than just any connected structure?

2. What is a leaf?