Data Structures
Trees: Binary Tree Fundamentals
Difficulty: Beginner
Every web page you load is a tree (the DOM), every directory you cd into is a tree, every JSON document with nested objects is a tree, and every arithmetic expression a compiler parses is a tree. Binary Tree Fundamentals turns that...
Trees: Binary Tree Fundamentals
Every web page you load is a tree (the DOM), every directory you cd into is a tree, every JSON document with nested objects is a tree, and every arithmetic expression a compiler parses is a tree. Binary Tree Fundamentals turns that ubiquitous shape into a precise data structure where each node has at most two children, named left and right.
This lesson covers the vocabulary you need for the rest of the curriculum (root, leaf, parent, child, sibling, depth, height), the four common shape categories (full, complete, perfect, balanced) and the degenerate case that collapses to a chain, all four canonical traversals (preorder, inorder, postorder, and level-order BFS), and both recursive and iterative implementations of each. You will also analyze why traversals are O(n) time but only O(h) space when written recursively.
In Queue & Deque, you saw that a FIFO queue processes items in arrival order; level-order traversal is exactly that pattern applied to tree nodes. In Hash Map (Dictionary) Basics, the bucket-by-key idea reappears here when you store parent-pointer mappings or memoize subtree results during a traversal.
With binary trees in your toolkit, Binary Search Tree (BST) layers an ordering invariant on top to turn the same shape into a logarithmic-time search structure.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define tree terminology (root, leaf, parent, child, sibling, depth, height) and explain each with a diagram.
Distinguish between full, complete, perfect, balanced, and degenerate binary trees.
Implement a binary tree node class in JavaScript and Python.
Perform inorder, preorder, postorder, and level-order traversals both recursively and iteratively.
Analyze time and space complexity of tree traversals.
Identify real-world applications of binary trees and choose the right traversal for a given problem.
Why This Matters
01
Trees are the foundation for BSTs, heaps, tries, segment trees, and virtually every hierarchical data structure -- mastering binary trees unlocks the entire tree family.
02
Tree traversals (inorder, preorder, postorder, level-order) are among the most commonly tested topics in technical interviews, appearing in problems like path sums, serialization, and lowest common ancestor.
03
Real-world systems are built on trees: file systems use directory trees, HTML uses the DOM tree, compilers use abstract syntax trees, and databases use B-trees for indexing.
Key Terms
8 terms you'll encounter in this lesson
Root
The topmost node of a tree with no parent. Every tree has exactly one root, and all other nodes are descendants of it.
Leaf
A node with no children (both left and right are null). Leaves are the endpoints of any path from the root.
Depth
The number of edges from the root to a given node. The root has depth 0, its children have depth 1, and so on.
Height
The number of edges on the longest path from a node down to a leaf. A leaf has height 0. The height of the tree is the height of the root.
Binary Tree
A tree where each node has at most two children, referred to as the left child and the right child.
Inorder Traversal
A depth-first traversal that visits the left subtree, then the current node, then the right subtree. For a BST, this produces sorted output.
Level-Order Traversal
A breadth-first traversal that visits all nodes at depth d before visiting any node at depth d+1, using a queue.
Complete Binary Tree
A binary tree where every level is fully filled except possibly the last, which is filled from left to right. Heaps use this structure.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Depth and height are the same thing"
Depth is measured from the root DOWN to a node (root has depth 0). Height is measured from a node UP to its deepest leaf (leaves have height 0). For the root node specifically, the height of the root equals the height of the tree, but depth of the root is always 0.
"A complete binary tree is the same as a full binary tree"
A full binary tree requires every node to have exactly 0 or 2 children. A complete binary tree requires all levels to be fully filled except the last, which fills left-to-right. A tree can be complete but not full (e.g., last level has a node with only a left child).
"Inorder traversal always gives sorted output"
Inorder gives sorted output only for Binary Search Trees (BSTs), where left < root < right. For a general binary tree, inorder visits left-root-right but the output is not necessarily sorted.
"Tree traversal is always O(log n)"
Every traversal visits ALL n nodes, so traversals are O(n) time. O(log n) applies to operations like search in a balanced BST, where you only visit nodes along one path from root to leaf.