Free lesson · DSA Mastery - Interview Prep, End to End
Introduction to Binary Trees
Introduction to Binary Trees
A binary tree is the first non-linear data structure in this course. Until now, every structure has been a sequence - arrays, strings, linked lists - where each element has at most one successor. A binary tree breaks that line into a branching hierarchy: every node holds a value and points to up to two children, a left and a right. This single change unlocks an enormous family of problems, because hierarchy is everywhere in computing - file systems, expression parsers, database indexes, decision processes, the DOM of a web page. This section builds the complete toolkit for binary trees, organized around the four traversal orders (level, preorder, inorder, postorder) that determine the sequence in which you visit nodes. Choosing the right traversal for a problem is the central skill, and this opening topic establishes the vocabulary, the node definition, and the recursive mental model that the other 46 topics build on.
The insight that makes trees tractable: a tree is recursive by nature. Each child of a node is itself the root of a smaller tree (a subtree). So almost every tree algorithm has the same shape - do something with the current node, then recurse into the left and right subtrees - and the only real decisions are what you do at each node and when you do it relative to the recursion.
The Node Definition
Throughout this section, a binary tree node is defined as follows. This is the exact structure every problem assumes:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
This Java class defines a binary tree node. Each node stores an integer value and two references, left and right, pointing to its child nodes. A null child means no subtree on that side.
A node's left or right is null when that child is absent. The whole tree is referenced by a single pointer to its root node; a null root means an empty tree, the base case that nearly every recursive tree method must handle first.
The Vocabulary
A handful of terms appear in every tree problem. Pinning them down now prevents confusion later:
- Root - the single topmost node, with no parent.
- Leaf - a node with no children (both
leftandrightarenull). - Parent / child - a node directly above / below another along an edge.
- Edge - the link between a parent and a child.
- Height of a node - the number of edges on the longest path from that node down to a leaf. A leaf has height 0.
- Depth of a node - the number of edges from the root down to that node. The root has depth 0.
- Height of the tree - the height of its root.
- Subtree - any node together with all of its descendants; itself a valid binary tree.
- Level - all nodes at the same depth.
Important: Height and depth are easy to confuse. Depth measures distance down from the root; height measures distance up from the deepest leaf. A leaf is at height 0 but may be at large depth; the root is at depth 0 but has the largest height. Many problems hinge on which one you actually need.
A Canonical Example Tree
This section uses one running example tree wherever a concrete shape helps. Keep it in mind:
graph TD
A((1)) --> B((2))
A --> C((3))
B --> D((4))
B --> E((5))
C --> F((6))
C --> G((7))
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
This diagram shows the canonical example tree. The root is one, with children two and three. Node two has children four and five; node three has children six and seven. The four leaf nodes are four, five, six, and seven.
Here node 1 is the root (depth 0), nodes 2 and 3 are at depth 1, and nodes 4–7 are leaves at depth 2. The tree's height is 2. Each of node 2 and node 3 roots a subtree of three nodes.
The Four Traversal Orders
A traversal is an order for visiting every node exactly once. There are four standard ones, and this entire section is organized around them because the traversal you choose dictates how naturally a problem's solution falls out.
Breadth-first (level order). Visit nodes level by level, top to bottom, left to right: 1, 2, 3, 4, 5, 6, 7. Implemented with a queue, not recursion. This is the right tool when a problem cares about levels or distance from the root - depth, width, right-side view, level averages.
Depth-first comes in three flavors, distinguished by when you visit the current node relative to its subtrees:
- Preorder - node, then left subtree, then right subtree:
1, 2, 4, 5, 3, 6, 7. Visit the node before descending. Natural for copying a tree, serializing it, or building paths from the root downward. - Inorder - left subtree, then node, then right subtree:
4, 2, 5, 1, 6, 3, 7. For a binary search tree, inorder visits values in sorted order - a fact that powers many BST problems. - Postorder - left subtree, then right subtree, then node:
4, 5, 2, 6, 7, 3, 1. Visit the node after both subtrees. Natural when a node's answer depends on results computed from its children - heights, diameters, subtree sums.
graph TD
A["traversal orders on the example tree"] --> B["Level order (BFS): 1 2 3 4 5 6 7"]
A --> C["Preorder (node, L, R): 1 2 4 5 3 6 7"]
A --> D["Inorder (L, node, R): 4 2 5 1 6 3 7"]
A --> E["Postorder (L, R, node): 4 5 2 6 7 3 1"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
This diagram lists the four traversal orders applied to the example tree. Level order visits one, two, three, four, five, six, seven. Preorder visits one, two, four, five, three, six, seven. Inorder visits four, two, five, one, six, three, seven. Postorder visits four, five, two, six, seven, three, one.
Note: Preorder, inorder, and postorder differ only in where the "visit the node" step sits relative to the two recursive calls - before, between, or after. That one positional choice is the whole difference, and recognizing which position a problem needs is most of the battle in tree problems.
The Recursive Template
Nearly every depth-first tree method follows the same skeleton: handle the empty case, then combine the current node with the results of recursing on its children. Here is the shape, using a height computation as the example:
public static int height(TreeNode root) {
if (root == null) return -1; // base case: empty tree has height -1
int leftHeight = height(root.left); // solve the left subtree
int rightHeight = height(root.right); // solve the right subtree
return 1 + Math.max(leftHeight, rightHeight); // combine at the current node
}
This Java code computes a tree's height recursively. An empty tree returns negative one. Otherwise it finds the height of each subtree and returns one plus the larger, combining the children's results at the current node.
The root == null check is the base case that stops the recursion; forgetting it is the most common source of null-pointer crashes in tree code. The two recursive calls solve the subproblems, and the final line combines them - this is postorder in disguise (both children before the node). Swap the order of those three steps and you get preorder or inorder instead.
Why Trees Matter In Interviews
Tree problems are among the most common in technical interviews, and for good reason: they test recursion fluency, force you to reason about base cases and combination logic, and have clean, bounded solutions that fit a 45-minute window. A strong grasp of the four traversals and the recursive template lets you decompose almost any tree problem quickly - which traversal exposes the structure I need, what do I compute at each node, and how do I combine the children's answers? Almost everything in this section is an application of those three questions.
Variations & Follow-ups
When should I use BFS versus DFS?
Use BFS (level order) when the problem is about levels or breadth: depth, width, level-by-level grouping, the nearest node to the root, or anything where "distance from the root" matters. Use DFS (preorder/inorder/postorder) when the problem is about paths, subtree properties, or values computed from children. Many problems can be solved either way, but one is usually far more natural - recognizing which saves significant effort.
Why is an empty tree's height -1 and not 0 here?
Defining an empty tree's height as -1 makes a single leaf's height come out to 1 + max(-1, -1) = 0, matching the "leaf has height 0" convention (height counts edges). Some texts count nodes instead and use 0 for empty and 1 for a leaf. Both are valid; just be consistent and state your convention. This course counts edges, so empty is -1 and a leaf is 0.
What makes a binary tree a binary search tree?
A binary search tree (BST) adds an ordering invariant: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That invariant is what makes inorder traversal produce sorted output and enables O(log n) search in a balanced BST. Several problems in this section involve BSTs (validation, kth smallest, sorted-array construction); the dedicated BST section that follows goes deeper.
How deep can the recursion go?
The recursion depth equals the tree's height. For a balanced tree of n nodes that's O(log n) - perfectly safe. But a degenerate tree (essentially a linked list, every node having one child) has height O(n), and recursing n levels deep can overflow the call stack for large n. When that's a risk, an explicit stack (iterative traversal) avoids the limit - a tradeoff several later topics revisit.
Why This Topic Matters
This introduction is the foundation for all 47 topics in the section. The node definition, the height/depth vocabulary, the four traversal orders, and the recursive template are the shared language of every tree problem that follows. Internalizing "do something at the node, recurse left, recurse right - and the only question is what and when" turns the apparent variety of tree problems into variations on one pattern. The recursion-as-subtree-decomposition mindset is the single most important idea to carry forward.
The next sub-group, Level Order, applies breadth-first traversal to problems that care about a tree's levels. It opens with Maximum Depth of Binary Tree: find the number of levels from the root down to the deepest leaf. It's the gentlest possible first problem - solvable in a few lines by either the recursive height template above or a level-counting BFS - and it cements the two traversal styles side by side before the level-order problems grow more elaborate.