Binary Trees & Tree Terms
Root, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A family tree turned upside down. At the top is one ancestor, the root. Each person can have children, those children have children, and so on. Unlike a linked list, a tree branches: it is non-linear and hierarchical.
In a binary tree, each node has at most two children: a left and a right.
struct Node {
int data;
Node* left;
Node* right;
};The vocabulary
| Term | Meaning |
|---|---|
| Root | the top node; it has no parent |
| Parent / child | a node and the nodes directly below it |
| Siblings | children of the same parent |
| Leaf | a node with no children |
| Internal node | a node with at least one child |
| Ancestor / descendant | anything on the path up / down |
| Subtree | a node plus all its descendants |
| Degree | number of children of a node |
| Depth of a node | edges from the root down to it (root depth = 0) |
| Level | all nodes at the same depth |
| Height of a node | edges on the longest path down to a leaf |
| Height of the tree | height of the root |
Special shapes
- Full: every node has 0 or 2 children.
- Complete: every level is full except possibly the last, which is filled from the left. (Heaps in Chapter 8 are complete trees.)
- Perfect: every level is completely full. A perfect tree of height h has 2^(h+1) − 1 nodes.
Thinking recursively
Every tree is “a root plus a left subtree plus a right subtree”. So most tree functions look like this:
int f(Node* r) {
if (r == nullptr) return /* base value */;
return /* combine */ (r, f(r->left), f(r->right));
}03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Step through to see each term highlighted on the same tree.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* make(int x, Node* l = nullptr, Node* r = nullptr) { return new Node{x, l, r}; }
int countNodes(Node* r) { return r ? 1 + countNodes(r->left) + countNodes(r->right) : 0; }
int countLeaves(Node* r) {
if (!r) return 0;
if (!r->left && !r->right) return 1;
return countLeaves(r->left) + countLeaves(r->right);
}
int height(Node* r) { // edges on the longest root-to-leaf path
if (!r) return -1; // empty tree: -1, single node: 0
return 1 + max(height(r->left), height(r->right));
}
int depthOf(Node* r, int x, int d = 0) { // -1 if not found
if (!r) return -1;
if (r->data == x) return d;
int L = depthOf(r->left, x, d + 1);
return L != -1 ? L : depthOf(r->right, x, d + 1);
}
void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }
int main() {
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// / \
// 7 8
Node* root = make(1, make(2, make(4), make(5, make(7), make(8))), make(3, nullptr, make(6)));
cout << "nodes: " << countNodes(root) << "\n";
cout << "leaves: " << countLeaves(root) << "\n";
cout << "height: " << height(root) << "\n";
cout << "depth of 7: " << depthOf(root, 7) << "\n";
destroy(root);
}nodes: 8 leaves: 4 height: 3 depth of 7: 3
05Complexity
| count nodes / leaves | O(n): visits every node once |
|---|---|
| height | O(n) |
| find a value (no ordering) | O(n) |
| Extra space | O(h) recursion stack, where h is the height |
A binary tree with n nodes has height between ⌊log₂ n⌋ (perfectly balanced) and n − 1 (a straight line). A perfect tree of height h has 2^(h+1) − 1 nodes.
06Watch
Binary Tree
Why this one: Every tree term, plus full/complete/perfect binary trees, with clear drawings.
07Exam lens
Likely questions
- Define: root, leaf, internal node, sibling, ancestor, descendant, depth, height, level, degree.
- Draw a full, a complete and a perfect binary tree. How do they differ?
- What is the maximum number of nodes at level k? In a binary tree of height h?
- Write recursive functions to count the nodes and compute the height of a binary tree.
Common mistakes
- Mixing up depth (from the root down to a node) and height (from a node down to its deepest leaf).
- Not stating your height convention. Here, a single node has height 0 and an empty tree −1. Some books count nodes instead of edges.
- Thinking "complete" and "full" mean the same thing.
- Forgetting the
nullptrbase case in recursive tree functions.
08Quick check
09Practice
🟢 Trace by hand
Draw the tree: A has children B, C. B has D, E. C has right child F. E has left child G. List leaves, internal nodes, the height of the tree, the depth of G, and the siblings of D.
Show answer
- Leaves: D, G, F
- Internal: A, B, C, E
- Height: 3 (A → B → E → G)
- Depth of G: 3
- Sibling of D: E
🟡 Implement it
Write int countInternal(Node* r) and int sumAll(Node* r), and bool isFull(Node* r) (every node has 0 or 2 children).
Hint
Each one is "handle nullptr, handle this node, recurse on left and right". For isFull: a node with exactly one child returns false.
Solution
bool isFull(Node* r) {
if (!r) return true;
if (!r->left != !r->right) return false; // exactly one child
return isFull(r->left) && isFull(r->right);
}🔴 Solve problems
Hint
Like
height(), but LeetCode counts nodes, so return 0 for nullptr.Hint
Both null → true; one null → false; else compare values and recurse on both sides.
Hint
Swap left and right, then recurse on both.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.