Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Trees and their properties

Clear, exam-focused notes on trees: definitions (rooted/unrooted), properties, key theorems (edges = n−1, equivalent characterizations), formulas for m-ary and binary trees, worked examples (proof by induction, numeric counts, traversal trace), common mistakes and quick-check questions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Trees are a basic data structure and mathematical object used by engineers in file systems, compiler parse trees, network routing, hierarchical design, and many algorithms (searching, shortest paths, spanning trees). Understanding tree properties helps you prove correctness and compute sizes, heights and memory needs for implementations.

Key ideas

Start with graphs. A graph is an ordered pair (V, E) where V is a set of vertices and E is a set of edges. We now define trees and related terms.

  • Tree (undirected, finite): A graph T = (V, E) is a tree if it is connected and acyclic (no simple cycles). We assume finite |V| = n unless stated otherwise.

  • Rooted tree: A tree with one specially designated vertex called the root. In textbooks, rooted means we consider parent-child relationships derived from the root.

  • Parent and child: In a rooted tree, if there is an edge from vertex u to v and u is closer to the root than v, then u is the parent of v and v is a child of u.

  • Sibling: Two vertices with the same parent.

  • Leaf (or external node): A vertex of degree 1 in an unrooted tree; in a rooted tree a leaf is a vertex with no children.

  • Internal node: A non-leaf node; in a rooted tree an internal node has at least one child.

  • Degree: The number of incident edges of a vertex.

  • Path: A sequence of distinct vertices where consecutive vertices are joined by edges. The length of a path is the number of edges on it.

  • Height (of a rooted tree): The maximum length (number of edges) from the root to any leaf. Some books count nodes instead; here we use edges (state this in answers if different convention is used).

  • Depth (of a node): The length of the unique path from the root to that node.

  • m-ary tree: A rooted tree where each node has at most m children. Special case: binary tree (m = 2).

  • Full (proper/strict) m-ary tree: Every internal node has exactly m children. For binary trees, a full binary tree means every internal node has exactly 2 children.

  • Complete binary tree: All levels except possibly the last are completely filled, and the last level is filled from left to right.

  • Balanced binary tree (height-balanced): For every node, the heights of its left and right subtrees differ by at most 1; this implies height is O(log n) when node degrees are bounded.

Important equivalent characterizations (finite case). Let G be a finite undirected graph with n vertices. The following statements are equivalent (each implies the others):

  1. G is connected and acyclic. (Definition of tree.)
  2. G is connected and has exactly n − 1 edges.
  3. G is acyclic and has exactly n − 1 edges.
  4. Any two vertices of G are connected by exactly one simple path.

Sketch of equivalence proof (standard exam derivation):

  • (1) ⇒ (2): A connected acyclic graph on n vertices has exactly n − 1 edges; remove a leaf iteratively and apply induction to justify this rigorously. Provide a full induction proof in exams.
  • (2) ⇒ (4): If connected and edges = n − 1, there cannot be two distinct simple paths between two vertices because their union would create a cycle, contradicting the fact that a connected n-vertex graph with n − 1 edges is acyclic (otherwise, removing an edge from a cycle would leave a connected graph with fewer than n − 1 edges, which is impossible). Hence uniqueness of path.
  • (4) ⇒ (1): If exactly one simple path between any pair, then graph is connected and cannot have a cycle (a cycle would give two different paths between vertices on cycle).
  • (3) ⇒ (2): If G is acyclic with exactly n − 1 edges, then G must be connected; otherwise, a forest on n vertices with c ≥ 2 components has at most n − c ≤ n − 2 edges (summing over components), contradicting e = n − 1.

Counting relations (standard derivations to remember):

  • For any tree with n vertices, number of edges e = n − 1. (Assume finite tree.)

  • In a full m-ary tree with i internal nodes and l leaves: total nodes n = i + l, and n = 1 + i·m. The precise relation for a full m-ary tree where every internal node has exactly m children is: l = (m − 1)·i + 1. (Derivation: count edges in two ways: each non-root node has exactly one parent so edges = n − 1. Also edges = m·i because each internal node contributes m children; equate m·i = n − 1 = i + l − 1 → l = (m − 1)·i + 1.)

  • Maximum nodes in an m-ary tree of height h (height = number of edges on longest root-to-leaf path) when all levels 0..h are full: n_max = (m^(h+1) − 1)/(m − 1). For binary m = 2 this gives n_max = 2^(h+1) − 1.

How to draw tree diagrams in exam answers (describe exactly):

  • For a rooted binary tree with root A and two children B (left), C (right): draw a point labelled A at top, draw two downward slanted lines to points labelled B (left) and C (right). For subtrees, draw similar child branches below B and C. Label edges implicitly by parent-child relation; do not draw arrowheads unless emphasising root direction.

Formulas

e = n − 1 — e is number of edges, n is number of vertices (nodes); unit: dimensionless; applies to finite undirected trees.

l = (m − 1)·i + 1 — l is number of leaves, i is number of internal nodes, and in a full m-ary tree m is the fixed number of children per internal node (applies only when every internal node has exactly m children); unitless.

n = i + l — total nodes n equals internal nodes plus leaves; unitless; applies to any rooted tree partitioning nodes into internal and leaves.

n_max = (m^(h+1) − 1) / (m − 1) — maximum nodes in a rooted m-ary tree of height h (levels 0..h full); m > 1; unitless. For the degenerate case m = 1, n_max = h + 1.

n_max_binary = 2^(h+1) − 1 — special case for m = 2; unitless.

Note: In traversal algorithms (preorder, inorder, postorder) there is syntax-like recurrence: Preorder(root): visit root; Preorder(left); Preorder(right) — applies to binary trees.

Worked examples

Example 1 — Proof that a finite tree with n vertices has n − 1 edges (induction). Question: Prove e = n − 1 for any finite tree with n vertices. Answer (induction on n):

  1. Base n = 1: tree with a single vertex has e = 0, and 0 = 1 − 1 holds.
  2. Inductive step: Assume all trees with k vertices have k − 1 edges. Let T be a tree with k + 1 vertices. Since T is finite and connected with no cycles, T has at least one leaf v (vertex of degree 1). Remove v and its incident edge; remaining graph T' has k vertices and is still a tree (removing a leaf preserves connectedness of the remaining vertices and keeps the graph acyclic). By induction, T' has k − 1 edges. Adding back v and its one edge gives e(T) = (k − 1) + 1 = k = (k + 1) − 1. Thus holds for k + 1. QED.

Example 2 — Numbers in a full binary tree. Question: A full binary tree has 13 internal nodes. Find number of leaves and total nodes. Answer:

  • For a full binary tree, m = 2, so l = (2 − 1)·i + 1 = i + 1.
  • Given i = 13, leaves l = 13 + 1 = 14.
  • Total nodes n = i + l = 13 + 14 = 27. Final answers: leaves = 14, total nodes = 27. (Units: nodes.)

Example 3 — Traversal trace (small binary tree). Question: Draw the tree and give preorder, inorder, postorder sequences. Draw (describe): Root labelled A. A has left child B and right child C. B has left child D and right child E. C has right child F only. So structure: level 0: A; level1: left B, right C; level2 under B: left D, right E; under C: right F. Compute traversals step-by-step:

  • Preorder (visit root, then left subtree, then right subtree): Visit A → traverse B subtree: visit B → D → E → then traverse C subtree: visit C → (left empty) → F. Result: A, B, D, E, C, F.
  • Inorder (left, root, right): For A: inorder(B) → A → inorder(C). inorder(B): D → B → E. inorder(C): (left empty) → C → F. Result: D, B, E, A, C, F.
  • Postorder (left, right, root): For A: postorder(B) → postorder(C) → A. postorder(B): D, E, B. postorder(C): F, C. Result: D, E, B, F, C, A. Final sequences: Preorder: A B D E C F; Inorder: D B E A C F; Postorder: D E B F C A.

Common mistakes

  • Applying the full m-ary formula l = (m − 1)·i + 1 to non-full trees (it requires every internal node to have exactly m children).
  • Mixing height measured in nodes vs edges; state which you use.
  • For complete binary trees, assuming last level can have gaps in middle; it must be filled from left.
  • For traversal outputs, writing node order without tracing the recursive steps; always show the recursion or mark visited nodes on the diagram.

For your exam

Types of questions you will see:

  • Definitions and short notes: define tree, rooted tree, leaf, internal node, binary tree, full/complete/balanced, height/depth. A full-marks answer lists definitions and simple diagrams.
  • Proofs/derivations: prove e = n − 1 by induction; derive l = (m − 1)·i + 1 for full m-ary trees; derive n_max formula. Full marks require clear statement of assumptions and step-by-step algebra.
  • Numericals: given i or h find l and n; given a tree draw and compute traversals. Show each formula used and substitute numbers, carry units (nodes) and give final bold numeric answers.
  • Diagrams: be ready to draw labeled rooted trees and mark depths/heights; to show uniqueness of path draw two different paths and show cycle contradiction.
  • Programs/algorithms: trace recursive traversal routines for a given tree; write short pseudo-code for preorder/inorder/postorder and show output on test tree.

What full-marks answers include: clear definitions (bold when asked), statement of assumptions (finite, undirected, rooted or not), correct formula used and derivation or citation, step-by-step algebra or induction, and a neat labelled diagram when required.

Quick check

  1. What is a leaf in a rooted tree?
  2. In a full ternary (m = 3) tree with 10 internal nodes, how many leaves?
  3. Give one equivalent property of a tree other than "connected and acyclic".

Answers: 1. A node with no children. 2. l = (3 − 1)·10 + 1 = 21. 3. The graph is connected and has n − 1 edges (or exactly one simple path between any two vertices).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?