A structure that branches instead of lining up: items hang in levels under a single root, and a balanced tree holding a million items is only 20 levels deep.
A structure that branches instead of lining up: items hang in levels under a single root, and a balanced tree holding a million items is only 20 levels deep.
The hashmaps page ended with a confession: hashing buys its O(1) lookups by destroying order completely. But plenty of problems want both: find any value fast, and also walk everything in sorted order on demand. The structure that manages both isn't a line at all. It branches.
A tree is a hierarchical data structure made of nodes connected by lines called edges. It starts with a single root node at the top, and each node can have zero or more child nodes beneath it, which creates distinct levels. Trees don't contain any cycles, so there's only one path from the root to any other node. That property makes trees a natural fit for representing hierarchy, like file systems or family trees, and for efficient searching. One caveat the family tree picture hides: in a data structure tree, every node has exactly one parent. No node descends from two.
Here's the number that makes trees worth learning: a balanced tree holding 1,000,000 nodes can find any value in about 20 steps, not a million. The secret is that each step down discards half of what remains: 1,000,000 becomes 500,000, then 250,000, and twenty halvings later there's a single node left.
Tree operations behave very differently depending on how the tree is shaped. In a balanced tree, inserting, deleting, and searching usually take O(log n) time, where n is the number of nodes. We get to skip whole subtrees as we descend, which is what makes this fast. In an unbalanced tree, the same operations can degrade to O(n) in the worst case because we may have to walk every node. Here are the common operations on a balanced binary tree:
| Operations | Time | Space |
|---|---|---|
| Insert | O(n) | O(h) |
| Delete | O(n) | O(h) |
| Search | O(n) | O(h) |
| Get Height | O(n) | O(h) |
| Pre-order | O(n) | O(h) |
| In-order | O(n) | O(h) |
| Post-order | O(n) | O(h) |
| Level-order | O(n) | O(w) |
The O(log n) complexity in balanced binary trees comes from their structure. At the root, we have access to every node. Each level down halves the number of nodes we still need to consider, from n to n/2. The number of times you can halve n before reaching 1 is literally the definition of log₂(n). Because we quickly focus on a small portion of the tree with each step, many tree operations end up logarithmic. And log₂(1,000,000) is about 20, which is exactly where those twenty steps came from.
Tree nodes are the building blocks of a tree. A node in a binary tree typically has three parts:
val holds the data you want to store (a number, a string, etc.).left pointer refers to the left child node.right pointer refers to the right child node.If a node has no children, its left and right pointers are set to null. That's enough to wire up the parent-child relationships that make up the tree:
Time to name the parts. Nodes and edges build the whole thing: the root sits at the top, children branch downward from it, and each level down adds another layer of parent-child relationships. The main pieces of a tree are:
Different kinds of trees take different shapes. For example, a node in a general tree can have any number of children, not just two. The shape changes the performance of a tree. Keeping subtrees roughly the same depth (a balanced tree) tends to keep operations fast. The exact tradeoffs depend on which type of tree you're using.
A binary tree is a hierarchical data structure where each tree node can have up to two children: a left child and a right child. There are two core rules:
Binary trees can't have any cycles. There's only one path from the root to any node. You can't start at a node, follow some edges, and end up back where you started. This is what keeps the tree a tree, and it's why traversals don't loop forever.
N - 1 EdgesA binary tree with N nodes has exactly N - 1 edges. Every node except the root has exactly one edge connecting it to its parent. Since N - 1 of the N nodes have a parent, there are N - 1 edges total.
Binary trees are the foundation for more advanced trees like Binary Search Trees (BST) and AVL trees. They show up in expression parsing, data compression, and efficient search and sort algorithms. Binary trees have a few notable variants:
Performance comes down to balance: a balanced binary tree keeps search, insert, and delete at O(log n), while a completely unbalanced one drags them down to O(n).
A Binary Search Tree (BST) is a binary tree with one extra rule: for every tree node, all values in its left subtree are smaller, and all values in its right subtree are larger than the node's own value. That rule applies to every node, which gives the tree an ordered structure. The order is what makes searching, inserting, and deleting fast.
For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This ordering is what makes search fast and what defines the tree's shape.
BSTs usually don't allow duplicate values. If you do need duplicates, you handle them by storing a count on each node or by picking a consistent rule for where duplicates go (always left, always right, etc.).
Because BSTs are ordered, search, insert, and delete typically run in O(log n) time on average. BSTs also support in-order traversal, which visits nodes in ascending order. This is handy for sorting and similar tasks:
| Operations | Time | Space |
|---|---|---|
| Insert | O(h)* | O(1) |
| Delete | O(h)* | O(1) |
| Search | O(h)* | O(1) |
| Get Minimum | O(h)* | O(1) |
| Get Maximum | O(h)* | O(1) |
| In-order | O(n) | O(h) |
One thing to keep in mind: these O(log n) times are the average case. Try this before reading on: insert 1, 2, 3, 4, 5 into an empty BST, in that order, and sketch the shape you get. Every new value is larger than the last, so every insert turns right. The result is a tree people call skewed: a chain, basically a linked list standing on end, where operations degrade to O(n). Sorted input, the case that feels like it should be the easy one, is exactly what ruins a naive BST. Self-balancing trees like AVL and Red-Black were built to prevent this: they keep the tree balanced and the operations at O(log n).
The depth of a node in a binary tree is the number of edges from the root to that node. Put simply, it's how many steps it takes to get from the top of the tree to that node. The root has a depth of 0, its immediate children have a depth of 1, and so on. The depth increases by 1 at each level as you move down the tree.
The height of a binary tree is the number of edges on the longest path from the root to a leaf. It's the farthest you can walk from the top of the tree down to a leaf. A tree with a single node has a height of 0, while an empty tree is usually defined to have a height of -1. The height of the tree is equal to the maximum depth of any node in the tree.
Calculating the depth and height uses a post-order traversal. We start at the bottom of the tree and work upward. For each node, we find the maximum depth of its left and right children, then add 1 to account for the current node. As we move up, the depth at each node grows, and by the time we reach the root we've found the maximum depth (which is the height of the tree).
The diameter of a binary tree is the number of nodes on the longest path between any two nodes in the tree. That path may or may not pass through the root. Put another way: pick the two nodes farthest apart and count the nodes on the walk between them. For a tree with a single node, the diameter is 1. For an empty tree, it's usually defined as 0.
To find the diameter, we need to find the two nodes that are farthest apart, so we use a post-order traversal. Our recursive function tracks two values at each node: the height of the current subtree and the longest diameter we've seen so far. At each node, the candidate path length is the sum of the left and right subtree heights plus 1 for the current node. This finds the diameter in a single pass and examines all possible paths without revisiting any nodes.
Trees show up everywhere: hierarchical data, search problems, and recursive algorithms. Here are a few tips for working with them well:
An efficient algorithm for finding elements in sorted data by halving the search space.
A method where a function calls itself to solve smaller instances of the same problem.
Algorithms for visiting all nodes in a tree data structure systematically.
An algorithmic technique for solving problems by exploring all possibilities.
An approach that makes the locally optimal choice at each step.
An algorithm for traversing graphs by exploring as far as possible along each branch.
An algorithm for traversing graphs level by level.
Dynamic programming applied to two-dimensional problems.
First, two checks from this page: where does the log n in tree search come from, and what input order turns a naive BST into a linked list? If both are easy, jump in. Trees are where recursion really clicks. Most of these problems are short to write but force you to think about what each recursive call should return. Work through them to internalize the patterns for traversal, BST invariants, path-aggregation, and tree DP:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
tree_nodes.py
# Definition of a binary tree node
class TreeNode:
def __init__(self, val: int = 0, left = None, right = None):
self.val = val
self.left = left
self.right = rightbinary_tree_depth.py
# Definition for a binary tree node
class TreeNode:
def __init__(self, val: int = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
# Base case: If there is no root, just return 0
if not root:
return 0
# Setting up DFS on tree
def dfs(root: Optional[TreeNode]) -> int:
# Base case: If root doesn't exist, then return 0
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
return max(left, right) + 1
# Call the DFS function
return dfs(root)tree_diameter.py
# Definition for a binary tree node
class TreeNode:
def __init__(self, val: int = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# Set up nonlocal variable res to store answer
res = 0
# Setting up DFS on binary tree
def dfs(root: Optional[TreeNode]) -> int:
# Base case: If there is no root, then return 0
if not root:
return 0
# DFS function calls for left and right children
left = dfs(root.left)
right = dfs(root.right)
# If value of left + right children is greater, update res
nonlocal res
if (left + right) > res:
res = (left + right)
return 1 + max(left, right)
# Call DFS function to store answer in res
dfs(root)
return res