Skip to content
Tutorials Center
My learning

Topics

Lesson 89 of 225 ยท Trees

Trees

Learn what a tree is: root, leaf, depth, height, subtrees, n-ary trees, ways to store them in Python, real uses and how recursion walks a tree.

Arrays, linked lists, stacks and queues are all linear: each element has one element before it and one after. But a lot of real information is not a line. A company has a CEO, managers and employees. A folder contains files and other folders. An HTML page nests elements inside elements. A decision process branches into "yes" and "no". All of these are hierarchies, and the data structure for a hierarchy is the tree.

This lesson is your map of the tree world. You will learn the vocabulary (root, parent, child, leaf, depth, height), write a general tree in Python, see three different ways to store one, and learn the most important technique of all: thinking about a tree recursively. Every later tree lesson (binary trees, traversals, binary search trees, heaps, tries) builds on these ideas.

What is a tree?

A tree is a set of nodes connected by edges so that:

  • there is exactly one special node called the root (at the top, by convention);
  • every other node has exactly one parent, the node directly above it;
  • there are no cycles, and every node can be reached from the root by exactly one path.
TEXT
                 Animals                 <- root (depth 0)
               /    |     \
         Mammals  Birds  Reptiles        <- depth 1
         /     \     |
       Dog    Whale  Owl                 <- depth 2

Tree pictures are drawn upside down compared with real trees: the root is on top and the branches grow downward. A tree with n nodes always has exactly n - 1 edges: every node except the root has one edge going up to its parent.

A tree is a special kind of graph: connected, with no cycles. That is why tree algorithms are the gentle introduction to graph algorithms.

Terminology

Term Meaning In the picture
Root the only node without a parent Animals
Parent / child the node directly above / below Mammals is the parent of Dog
Siblings nodes with the same parent Dog and Whale
Leaf a node with no children Dog, Whale, Owl, Reptiles
Internal node a node with at least one child Animals, Mammals, Birds
Ancestor / descendant any node on the path up to the root / down from a node Animals is an ancestor of Owl
Degree number of children of a node Animals has degree 3
Depth (level) of a node number of edges from the root to the node Owl has depth 2
Height of a node number of edges on the longest path down to a leaf Mammals has height 1
Height of the tree height of the root 2
Subtree a node together with all its descendants the subtree rooted at Mammals

Careful with depth and height: depth counts downward from the root, height counts downward to the deepest leaf. Some textbooks count nodes instead of edges (making a one-node tree have height 1). In this tutorial we count edges, so a single node has height 0. Always check which convention a problem uses.

A tree node in Python

For a general tree, where a node can have any number of children, the natural design is a node with a value and a list of children:

Python A general tree: building and printing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at how show works: it prints the current node, then calls itself on every child. That tiny function already contains the central idea of this lesson.

Thinking recursively

A tree is a recursive structure: every child of a node is itself the root of a smaller tree. This gives a template for almost every tree algorithm:

  1. Base case: an empty tree (or a leaf) has a trivial answer.
  2. Recursive case: solve the problem for each child's subtree, then combine the answers with the current node's own contribution.

If recursion is still shaky, revisit Recursion first. Here are the four most common questions about a tree, each answered with that template:

  • Size (number of nodes) = 1 + the sizes of all child subtrees.
  • Leaves = 1 if the node has no children, else the sum of leaves in the child subtrees.
  • Height = 0 for a leaf, else 1 + the maximum child height.
  • Sum of values = own value + the sums of child subtrees.
Python Size, leaves, height and depth by recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each function visits every node once, so each runs in O(n) time. The space is the recursion depth: O(h), where h is the height of the tree. For a balanced tree h is about log n, but for a tree shaped like a long chain h is n, and Python's default recursion limit of about 1,000 becomes a problem. In that case convert the recursion into a loop with an explicit stack, as shown below.

Finding paths

Another very common recursive pattern is returning the path from the root to a node. Return a list on success, and None when the node is not in this subtree. The parent adds itself to the front of whatever its child found.

Python Path from the root to a node

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three ways to represent a tree

The node-with-a-list design is the most readable, but it is not the only one. The right choice depends on what you do with the tree.

1. Nodes with child lists (above). Natural and flexible. Each node uses memory for its own list.

2. Parent array. Store only, for each node i, the index of its parent (and -1 for the root). It is very compact and perfect when you only walk upward (for example in Union-Find), but finding the children of a node needs a scan.

3. First child / next sibling. Every node stores just two pointers: its first child and its next sibling. Any tree, however many children each node has, is stored using nodes with exactly two links. This is also how you can turn a general tree into a binary tree.

TEXT
Animals                      parent array (index: name -> parent)
 |-- Mammals                 0 Animals  -> -1
 |    |-- Dog                1 Mammals  -> 0
 |    `-- Whale              2 Birds    -> 0
 |-- Birds                   3 Dog      -> 1
 |    `-- Owl                4 Whale    -> 1
 `-- Reptiles                5 Owl      -> 2
                             6 Reptiles -> 0
Python The same tree in three representations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Representation Children of a node Parent of a node Memory
Child lists O(1) to get the list O(1) if you store a parent link, else a search list per node
Parent array O(n) scan O(1) one integer per node
First child / next sibling O(number of children) not available without a parent link two links per node

Avoiding deep recursion

Recursive tree functions use one stack frame per level of depth. For very deep trees, use an explicit stack to walk the tree in a loop. The order in which you pop nodes decides the traversal order. A stack gives a depth-first walk, and a queue gives a breadth-first (level-by-level) walk. Both are covered in depth in Tree Traversals and Level-Order Traversal and Tree BFS.

Python Depth-first and level-by-level without recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where trees appear

  • File systems: directories contain files and other directories. Computing the size of a folder is a recursive sum over its subtree.
  • The DOM / XML / JSON: every HTML page is a tree of elements, and nested JSON is a tree of dictionaries and lists.
  • Parsing and compilers: expressions like 2 + 3 * 4 become a syntax tree whose shape fixes the order of operations.
  • Organization charts, taxonomies, menus, comment threads.
  • Efficient data structures: binary search trees and B-trees for fast search, heaps for priority queues, tries for words.
  • Decision trees and game trees in machine learning and AI, and the call tree of any recursive function.

Here is a file-system example that uses a nested dictionary as a tree: a string is a file with a size, a dictionary is a folder.

Python Folder sizes with a recursive sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Mixing up depth and height. Depth is measured from the root down to a node; height from a node down to its deepest leaf.
  • Forgetting the base case. A function that always recurses into node.children is fine for a leaf (the loop is empty), but a function that accesses node.left.value on a missing child crashes.
  • Edge versus node counting. A one-node tree has height 0 when counting edges and 1 when counting nodes. Read the definition in the problem.
  • Deep recursion on skewed trees. A chain of thousands of nodes needs an iterative approach.
  • Sharing child lists. Using children=[] as a default argument shares one list between all nodes. Use None and create a new list, as the code above does.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A tree has 12 nodes. How many edges does it have?

    Every node except the root has exactly one edge to its parent, so a tree with n nodes has n - 1 edges.
  2. 2. What is the depth of the root of a tree (counting edges)?

    Depth is the number of edges from the root to the node, so the root itself has depth 0.
  3. 3. Which description matches a leaf?

    A leaf has no children. The root is the node without a parent, and leaves can appear at different depths.
  4. 4. What is the height of a tree consisting of a single node (counting edges)?

    Height counts the edges on the longest downward path. A lone node has no edges, so its height is 0.
  5. 5. Which approach avoids RecursionError when walking a very deep tree?

    An explicit stack lives on the heap and is not limited by Python's recursion depth, so a loop can handle chains of any length.

Summary

  • A tree is a hierarchy of nodes with one root, one parent per other node, and no cycles; a tree with n nodes has n - 1 edges.
  • Key terms: root, parent, child, sibling, leaf, ancestor, descendant, degree, depth (from the root), height (to the deepest leaf), subtree.
  • Every subtree is a smaller tree, so most tree algorithms are recursive: handle the base case, solve for the children, and combine.
  • Size, leaf count, height and sums all run in O(n) time and O(h) stack space.
  • Trees can be stored as child lists, as a parent array, or with first-child/next-sibling links, each with different strengths.
  • Use an explicit stack or queue to walk very deep trees without recursion.

Next: Binary Trees, the most important special case where every node has at most two children.