Data Structures

Trees

What a tree data structure is: roots, nodes, parents and leaves, the one-parent rule, why loops break a tree, and how to build and walk one in Python code.

7 min read
5 questions
+35 XP
23 Nov 2025

Up nextBig O Notation

Write-up

Go deeper

A tree is a way of arranging data as a hierarchy: one item at the top, and everything else branching downwards from it. Folders on your computer, the elements of a web page, a JSON document and a company's org chart are all trees, and once you know the few rules that define one, you start to see them everywhere.

The parts of a tree

Take a cat café's staff chart. Boss Cat is at the top. Kitchen Cat and Floor Cat report to Boss Cat, and Snack Cat and Dish Cat report to Kitchen Cat. Here is that chart drawn as a tree:

Drawing the diagram…

flowchart TD B[Boss Cat] --> K[Kitchen Cat] B --> F[Floor Cat] K --> S[Snack Cat] K --> D[Dish Cat]

Boss Cat is the root; Floor Cat, Snack Cat and Dish Cat are leaves.Expand it to fill the screen. Zoom with the buttons or pinch, drag to pan.

Trees come with their own vocabulary, and nearly all of it is borrowed from family trees:

Node: one item in the tree. Each cat is a node.
Root: the single node at the top, with nothing above it. Here that is Boss Cat.
Edge: the link between a node and one directly below it.
Parent and child: Kitchen Cat is the parent of Snack Cat, and Snack Cat is a child of Kitchen Cat.
Siblings: nodes with the same parent, such as Snack Cat and Dish Cat.
Leaf: a node with no children. Floor Cat, Snack Cat and Dish Cat are leaves.
Subtree: any node together with everything below it. Kitchen Cat and its team form a small tree of their own.

Trees are usually drawn upside down compared with the ones outside: root at the top, leaves at the bottom.

The rules that make it a tree

Not every set of connected items is a tree. A tree follows three rules:

There is exactly one root. Everything starts from a single node.
Every other node has exactly one parent. A node can have any number of children, but only one node directly above it.
There are no loops. Following edges downwards, you can never arrive back at a node you have already passed.

Put those together and you get the property that makes trees so useful: there is exactly one path from the root to any node. To reach Snack Cat you go Boss Cat, then Kitchen Cat, then Snack Cat, and there is no other way. A neat side effect is that a tree with n nodes always has n - 1 edges, because every node except the root contributes exactly one edge, the one to its parent.

What breaks a tree

Say the café decides Snack Cat should also report to Floor Cat:

Drawing the diagram…

flowchart TD B[Boss Cat] --> K[Kitchen Cat] B --> F[Floor Cat] K --> S[Snack Cat] K --> D[Dish Cat] F --> S

There are now two different paths from Boss Cat down to Snack Cat.Expand it to fill the screen. Zoom with the buttons or pinch, drag to pan.

Snack Cat now has two parents, so the one-parent rule is broken and there are two routes from the top to Snack Cat. The structure is still perfectly valid data, but it is a graph, the more general shape where any node can connect to any other. Graphs are more flexible, and that flexibility is exactly what makes them harder to work with: code has to remember which nodes it has already visited, or it will count Snack Cat twice.

A loop breaks a tree in a worse way. If a node ever becomes its own ancestor (Boss Cat reporting to Snack Cat, say), code that walks 'down' the structure can go round forever.

Depth, height and subtrees

Two measurements come up constantly:

The depth of a node is how many edges sit between it and the root. Boss Cat has depth 0, Kitchen Cat depth 1, Snack Cat depth 2.
The height of a tree is the length of the longest path from the root down to a leaf. The café tree has height 2.

The subtree idea matters more than it first looks. Because every child is the root of a smaller tree, almost any question about a tree can be answered by asking the same question of each child and combining the answers. That is recursion, and it is why tree code is often surprisingly short.

Building one in code

The simplest way to model a tree is a node that holds its own value and a list of its children:

class Node:
    def __init__(self, name):
        self.name = name
        self.children = []
 
    def add(self, child):
        self.children.append(child)
        return child
 
 
boss = Node("Boss Cat")
kitchen = boss.add(Node("Kitchen Cat"))
boss.add(Node("Floor Cat"))
kitchen.add(Node("Snack Cat"))
kitchen.add(Node("Dish Cat"))

Each child appears in exactly one children list, which is the one-parent rule written in code. Now the recursive questions. How tall is the tree, and how many cats are in it?

def height(node):
    if not node.children:
        return 0
    return 1 + max(height(c) for c in node.children)
 
def count(node):
    return 1 + sum(count(c) for c in node.children)
 
print(height(boss))  # 2
print(count(boss))   # 5

A leaf has height 0. Any other node is one taller than its tallest child. The count works the same way: a node is one cat plus however many cats are in each of its subtrees.

Walking a tree

Visiting every node is called a traversal, and there are two main orders.

Depth-first goes as far down one branch as it can before backing up and trying the next. On the café tree that visits Boss Cat, Kitchen Cat, Snack Cat, Dish Cat, then Floor Cat. It falls naturally out of recursion, and it is what you want when you need to finish one branch before moving on, such as printing a folder listing with nested indentation.

Breadth-first visits the tree level by level: Boss Cat, then Kitchen Cat and Floor Cat, then Snack Cat and Dish Cat. It uses a queue instead of recursion, and it is the right choice when you want the node closest to the root, such as the nearest manager with a given skill.

Both visit every node exactly once, which is only guaranteed because a tree has no loops and no shared children.

Where you will meet trees

File systems. One main folder, with folders inside folders. Because each folder has exactly one parent, a path like /home/kitty/notes.txt names exactly one file.
Web pages. The browser turns HTML into the DOM, a tree with <html> at the root and every element nested inside exactly one parent element.
JSON and config files. Objects inside objects form a tree, which is why you can address any value with a path of keys.
Code itself. Compilers and interpreters turn source code into a syntax tree before they run or translate it.

A very common special case is the binary tree, where each node has at most two children. A binary search tree adds an ordering rule: smaller values go to the left, larger ones to the right. That lets a lookup skip half of the remaining tree at every step, so in a well-balanced tree finding a value takes about log n steps instead of n. If that notation is new, the Big O Notation page explains it.

Common mistakes

Treating a graph as a tree. If your data can give a node two parents (people with two managers, files tagged into several categories), tree code will visit those nodes twice. Check the data really follows the one-parent rule, or track visited nodes.
Assuming every tree is binary. Binary trees get most of the textbook attention, but most real trees, like folders and the DOM, let a node have any number of children.
Recursing into a very deep tree. Each level of recursion uses a little memory, and Python stops at a recursion limit (1,000 by default). For deep or untrusted trees, walk them with an explicit stack or queue instead.
Mixing up depth and height. Depth is measured from the root down to one node; height is measured across the whole tree, down to its deepest leaf.

Key takeaways

A tree has one root, every other node has exactly one parent, and there are no loops.
Those rules give exactly one path from the root to any node.
Give a node a second parent, or add a loop, and you have a graph, not a tree.
Every child is the root of its own subtree, so recursion fits trees naturally.
Folders, the DOM, JSON and syntax trees all use the same shape.

Code

See it in code

Build a tree and label its root, parents and leaves

Python

Builds a tree from TreeNode objects and walks it, printing each node's depth and whether it is the root, a parent or a leaf. Boss Cat is the root at depth 0, and Snack Cat, Dish Cat and Floor Cat are the leaves.

class TreeNode:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


root = TreeNode("Boss Cat", [
    TreeNode("Kitchen Cat", [
        TreeNode("Snack Cat"),
        TreeNode("Dish Cat"),
    ]),
    TreeNode("Floor Cat"),
])


def describe(node, depth=0):
    if depth == 0:
        role = "root"
    elif node.children:
        role = "parent"
    else:
        role = "leaf"
    label = f"{node.value} (depth {depth}, {role})"
    print("  " * depth + label)
    for child in node.children:
        describe(child, depth + 1)


describe(root)

Walk a tree depth-first and breadth-first

Python

Visits every node of the same tree in the two main orders. Depth-first prints Boss Cat > Kitchen Cat > Snack Cat > Dish Cat > Floor Cat; breadth-first goes level by level: Boss Cat > Kitchen Cat > Floor Cat > Snack Cat > Dish Cat.

from collections import deque


class TreeNode:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


root = TreeNode("Boss Cat", [
    TreeNode("Kitchen Cat", [
        TreeNode("Snack Cat"),
        TreeNode("Dish Cat"),
    ]),
    TreeNode("Floor Cat"),
])


def depth_first(node):
    order = [node.value]
    for child in node.children:
        order += depth_first(child)
    return order


def breadth_first(root):
    order = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        order.append(node.value)
        queue.extend(node.children)
    return order


print(" > ".join(depth_first(root)))
print(" > ".join(breadth_first(root)))

Check the three tree rules in JavaScript

JavaScript

Takes a list of parent-child edges and checks it is a tree: exactly one root, one parent per node and no loops. It prints true for the tree, then false when Snack Cat gets a second parent and false when a loop is added.

function isTree(edges) {
  const parent = new Map();
  const nodes = new Set();
  for (const [p, c] of edges) {
    if (parent.has(c)) return false; // two parents
    parent.set(c, p);
    nodes.add(p);
    nodes.add(c);
  }

  const roots = [...nodes].filter((n) => !parent.has(n));
  if (roots.length !== 1) return false; // not one root

  for (const node of nodes) {
    const seen = new Set();
    let at = node;
    while (parent.has(at)) {
      if (seen.has(at)) return false; // a loop
      seen.add(at);
      at = parent.get(at);
    }
  }
  return true;
}

const tree = [
  ["Boss Cat", "Kitchen Cat"],
  ["Boss Cat", "Floor Cat"],
  ["Kitchen Cat", "Snack Cat"],
  ["Kitchen Cat", "Dish Cat"],
];
const twoParents = [...tree, ["Floor Cat", "Snack Cat"]];
const withLoop = [...tree, ["Snack Cat", "Boss Cat"]];

console.log(isTree(tree)); // true
console.log(isTree(twoParents)); // false
console.log(isTree(withLoop)); // false

Up nextBig O Notation

What should we explain next?

Got a concept you want explained with cats? Tell us.