The binary tree
A tree is nodes in hierarchy: root at top, each pointing to children below. Binary tree restricts each node to at most 2 children (left, right). Trees fit recursion naturally - visit the node, then recursively process its left and right subtrees.
You know that a linked list is a chain of nodes, each pointing to the next. Now imagine a structure where each node points not to one next node, but to two: a left child and a right child. This is a tree. Instead of a linear chain, you get a branching structure—one root node at the top, spreading downward into leaves. Trees let you organize hierarchies (like a file system), and they fit recursion so naturally that processing a tree feels like breathing. In ten minutes you will know the vocabulary, the code representation, and why trees and recursion are inseparable—so that when you hit your first tree problem, you recognize the shape immediately.
After this lesson you can explain what a tree is, distinguish a binary tree from other trees, use the terminology (root, leaf, parent, child, depth, height, subtree, level), implement a node with left and right pointers, navigate a binary tree by following child pointers, and recognize when a tree is the right data structure.
What is a tree?
Why do we even need trees? Arrays and linked lists are flat—every element is equal in rank. But real problems have hierarchy: a file system has folders containing folders, a company has managers with reports, an expression has operators with sub-expressions. Trees capture that structure directly, and once you see the shape, you will recognize it everywhere.
A tree is a hierarchy of nodes connected by edges. One node is special: the root, at the top. Every other node has exactly one parent (the node pointing to it). A node can have zero, one, or more children (nodes it points to).
Visual:
1 (root)
/ \
2 3
/ \
4 5Here, node 1 is the root. Node 2 is the parent of 4 and 5. Node 4 is a child of 2. Nodes 4 and 5 are siblings (they share the same parent).
What is a binary tree?
A binary tree is a tree where each node has at most 2 children. We call them the left child and the right child. A node can have:
- No children (a leaf)
- One child (left only, or right only)
- Two children (both left and right)
The binary tree above:
1
/ \
2 3
/ \
4 5Node 1 has a left child (2) and a right child (3). Node 2 has two children. Node 3 has none. Nodes 4 and 5 are leaves.
Tree terminology
When you read algorithm descriptions or interview questions about trees, you will encounter these terms constantly. Getting them precise now saves confusion later—especially the depth/height pair, which trips up almost everyone the first time.
- Root: The topmost node (no parent).
- Leaf: A node with no children.
- Internal node: A node with at least one child.
- Parent / Child: If node A points to node B, A is the parent and B is the child.
- Sibling: Two nodes with the same parent.
- Ancestor / Descendant: Node A is an ancestor of B if A is on the path from B up to the root. B is a descendant of A.
- Level: All nodes at the same distance from the root are at the same level. The root is at level 0.
Depth vs. Height (this trips everyone up)
- Depth of a node = the number of edges from the root down to that node. The root has depth 0.
- Height of a node = the number of edges from that node down to its furthest leaf descendant. A leaf has height 0.
- Height of the tree = the height of the root.
Memory aid: Depth is how deep you’ve gone down from the root. Height is how tall the subtree reaches below you.
Example:
1 (depth=0, height=2)
/ \
2 3 (depth=1, height=1 for node 2; height=0 for node 3)
/ \
4 5 (depth=2, height=0 for both)Node 4 has depth 2 (two edges from root: 1→2→4) and height 0 (no children). Node 2 has depth 1 and height 1 (one edge down to its furthest leaf).
Subtrees and recursion
A subtree is any node plus all its descendants. The left subtree of a node is the subtree rooted at its left child. The right subtree is rooted at its right child.
A binary tree is defined recursively:
- An empty tree is a binary tree.
- A tree with a root and a left subtree (which is a binary tree) and a right subtree (which is a binary tree) is a binary tree.
This recursive definition is the key insight: to process any tree, you process the root, then recursively process the left subtree, then the right subtree. This structure is why recursion and trees are meant for each other.
Representing a node in code
In a linked list, each node held a value and a pointer to the next node. In a binary tree, each node holds a value and pointers to the left and right children:
class Node { constructor(value, left = null, right = null) { this.value = value; this.left = left; this.right = right; } } // Build the tree: // 1 // / \ // 2 3 // / \ // 4 5 let node4 = new Node(4); let node5 = new Node(5); let node2 = new Node(2, node4, node5); let node3 = new Node(3); let root = new Node(1, node2, node3); - L1 Node constructor stores value, left, and right.
- L7 Build bottom-up: leaves first.
- L13 Root is the entry point to the whole tree.
Navigating the tree by following pointers
To read the tree, you follow parent→child links. Each node is a step down:
// Access nodes by following left/right pointers let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3)); // Navigate to the left child of root let leftChild = root.left; // Node 2 // Navigate to the left child of node 2 let leftGrandchild = root.left.left; // Node 4 // Navigate to the right child of node 2 let rightGrandchild = root.left.right; // Node 5 // Each link is a single pointer hop console.log(leftChild.value); // 2 console.log(leftGrandchild.value); // 4 - L5 root.left follows the left pointer from root.
- L8 root.left.left hops through two pointers.
- L11 root.left.right hops left then right.
- L14 Each navigation accesses the value property.
A simple helper: checking if a node is a leaf
A leaf has no children (both left and right are null). Here is a small helper function:
function isLeaf(node) { return node.left === null && node.right === null; } let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3)); console.log(isLeaf(root.left.left)); // true (node 4 is a leaf) console.log(isLeaf(root.left)); // false (node 2 has children) console.log(isLeaf(root)); // false (root has children) - L1 A leaf is a node with no children.
- L2 Check if both pointers are null.
- L6 Construct the tree.
- L8 Node 4 has no children, so isLeaf returns true.
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3)); let target = root.left.right; // Navigate to node 5 console.log(target.value); Time complexity
Building the tree from scratch (creating n nodes) takes O(n) time. Navigating the tree by following pointer hops (e.g., root.left.right) takes O(1) per hop. Following a path of length d takes O(d). The isLeaf helper is O(1).
Time = O(1) per pointer hop; O(n) to build the entire tree.
Space complexity
Space is used to store the tree structure: each of the n nodes occupies O(1) space. The tree itself uses O(n) space in memory.
Space = O(n) for the tree structure itself. Individual operations like isLeaf use O(1) extra space.
What is the depth of a node?
What is the height of a node?
What is the height of a leaf node?
In code, how do you represent a binary tree node?
What is the worst-case height of a binary tree with 7 nodes?
▸lesson.inset.undefined
Depth ≠ Height. Depth measures distance from the root down to you. Height measures distance from you down to the furthest leaf. They point in opposite directions.
▸lesson.inset.undefined
Empty tree. A tree can be empty (no nodes). The height of an empty tree is sometimes defined as -1, sometimes as 0, depending on convention. Always check the definition in your problem.
▸lesson.inset.undefined
Draw a tree. Draw a binary tree with 5 nodes. Label the root, leaves, and one internal node. Then calculate the depth and height of each node. This is the fastest way to cement the terminology.
Why is a tree a natural fit for recursive algorithms?
A tree is a hierarchy of nodes with one root at the top. A binary tree restricts each node to at most 2 children: left and right. Trees use terminology: root, leaf, parent, child, sibling, ancestor, descendant, level. Depth is the number of edges from the root down to a node; height is the number of edges from a node down to its furthest leaf. A subtree is a node plus all its descendants. In code, represent a node as { value, left, right }, where left and right are null if there is no child. Navigate a tree by following left and right pointers from the root. A leaf is any node where both left and right are null. Binary trees are the foundation for heaps, binary search trees, and many other algorithms. Now when you see a node with left and right pointers, you will instantly read the whole subtree structure and know whether to go deeper or combine results on the way back up.
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.