The vocabulary every tree question assumes: root, leaf, height vs depth, levels, subtrees, and balanced vs complete vs full shapes.
0 of 6 lessons checked off
Introduction
What it is
A tree is a connected structure with no cycles: n nodes, exactly n − 1 edges, and exactly one path between any two nodes. One node is designated the root; edges fan out downward to children.
This page is deliberately about words — root, leaf, depth, height, level, subtree, balanced, complete, full — because every tree problem statement is written in them.
Why it matters
Trees model every hierarchy you touch: file systems, DOM/UI components, org charts, JSON documents, decision processes, and database indexes.
Misreading one term costs whole solutions: confusing height with depth, or balanced with complete, sends your code to the wrong subtree entirely.
How it works
Structurally, a node holds a value plus references to children — a linked list that branches.
Everything is recursive: a tree is a root plus smaller trees. Algorithms mirror that — handle the node, recurse on children, combine.
Where it's used
Your filesystem is a tree you navigate daily; HTML is parsed into the DOM tree; compilers build abstract syntax trees; databases answer range queries with B-trees.
In interviews
Terminology check-ins ('what's the height of a single node?'), counting nodes/leaves, and as the foundation for the binary-tree, BST, heap, and trie pages that follow.
Analogy: A family tree drawn upside down: one ancestor at the top (root), descendants branching below, and 'find your cousin' always has exactly one path through a common ancestor.
Interactive diagram
Step through the vocabulary on one small tree — including the height-vs-depth trap.
A tree
A tree is a hierarchy of nodes connected by edges, with exactly one path between any two nodes. No cycles, ever.
1 / 7
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
Three one-liners that establish the recursive rhythm used by every tree algorithm: base case on None, recurse on children, combine.
Measuring a tree: size, height, leaf count
1fromtypingimportOptional234classTreeNode:5def__init__(self,val:int=0,left:"Optional[TreeNode]"=None,6right:"Optional[TreeNode]"=None):7self.val,self.left,self.right=val,left,right8910defsize(root:Optional[TreeNode])->int:11"""Number of nodes. O(n)."""12ifrootisNone:13return014return1+size(root.left)+size(root.right)151617defheight(root:Optional[TreeNode])->int:18"""Edges on the longest root-to-leaf path. Empty tree: -1, leaf: 0."""
Time: O(n) each — every node visited onceSpace: O(h) recursion stack
Edge cases
Empty tree: size 0, height −1 (edge convention) or 0 (node-count convention) — STATE which you use.
Single node: height 0 by the edge convention.
Degenerate tree: recursion depth n — mind Python's limit.
Common mistakes
Mixing height conventions mid-solution (edges vs nodes) — off-by-one everywhere.
Counting a None child as a leaf.
Complexity analysis
Operation
Best
Average
Worst
Space
Traverse all nodes
O(n)
O(n)
O(n)
O(h)
Height / size / leaf count
O(n)
O(n)
O(n)
O(h)
Search (unordered tree)
O(1)
O(n)
O(n)
O(h)
h = height: log n balanced, n degenerate. The h-vs-n distinction is the whole story of tree performance.
What interviewers expect you to know
Definitions you will be tested on
Depth(node): edges from the ROOT to it. Height(node): edges to its deepest LEAF. Height(tree) = height(root) = depth of deepest node.
Level = depth + 1 in most texts (root at level 1) — confirm the convention when a problem uses 'level'.
Complete: all levels full except possibly the last, filled left to right (heap shape). Full: every node has 0 or 2 children. Balanced: height O(log n) (AVL-style: subtree heights differ ≤ 1).
A tree with n nodes has n − 1 edges; max nodes at depth d is 2ᵈ (binary); max nodes in height-h binary tree is 2^(h+1) − 1.
Follow-ups to expect
"Height of an empty tree?" — −1 with edge counting, 0 with node counting; naming both shows fluency.
"Why does everything cost O(h)?" — paths from root bound the work; balance decides whether h is log n or n.
Common mistakes
Height vs depth swapped
They point opposite ways. Depth is measured from the root; height toward the leaves. The deepest node has max depth and height 0.
Complete vs full vs balanced conflated
A heap needs COMPLETE; 'full' and 'balanced' are different claims. Using them interchangeably leads to wrong assumptions about shape.
Assuming balance
Unless stated, a binary tree can be a path. Quote O(h) and note h = n worst case.
Miscounting edges vs nodes
A tree with n nodes has n − 1 edges, and a leaf's height is 0 edges (or 1 node, depending on convention). Slipping between edge-counting and node-counting mid-derivation is the most common source of off-by-one errors.
Treating a leaf's children as real nodes
A leaf's left/right are None, not empty subtrees to recurse into blindly — every recursive tree function must guard `if node is None` first, or it crashes one level below the leaves.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.