TreesData structureaka rooted binary tree

Binary Tree

A hierarchical structure where every node has at most two children, the foundation of BSTs, heaps and expression trees.

▶ VisualizePattern: Breadth-First SearchPractice (4)
Progress

Definition

A binary tree is a set of nodes connected by parent-child edges where each node has at most two children, conventionally called left and right. One node, the root, has no parent; nodes with no children are leaves. The depth of a node is its distance from the root and the height of a tree is the longest root-to-leaf path.

A binary tree imposes no ordering on values by itself. Ordering constraints produce a Binary Search Tree; shape constraints produce a complete tree usable as a Binary Heap. What every binary tree shares is a naturally recursive definition: a tree is either empty or a node with two subtrees, which is why almost every tree algorithm is a few lines of recursion.

Common shape vocabulary: a full tree has 0 or 2 children per node, a complete tree is filled level by level left to right, a perfect tree has all leaves at the same depth (2^h - 1 nodes), and a balanced tree has height O(log n).

hierarchicalrecursiontraversalDFSBFS

Intuition

A mental model before the formal terms.

Picture a tournament bracket turned upside down or a family tree with at most two children per person. Getting from the root to any node means following a sequence of left/right turns; in a bushy tree with a million nodes that sequence is only about 20 turns long, but in a degenerate tree where every node has one child it is a million.

Traversals are just the order in which you "visit" each person while walking the family tree: inorder visits left branch, then the person, then right branch; preorder visits the person first; postorder visits the person last, after both branches have been dealt with.

How it works

  1. Each node stores a value plus left and right references (or child indices in an array-backed tree). An empty subtree is null.
  2. Depth-first traversals recurse: preorder (node, left, right) copies or serializes a tree; inorder (left, node, right) yields sorted order for a BST; postorder (left, right, node) computes sizes, heights and frees memory bottom-up.
  3. Breadth-first traversal (Breadth-First Search (BFS)) uses a Queue: push the root, then repeatedly pop a node, process it and push its children. Tracking the queue size per iteration gives level-by-level output.
  4. Most "compute something about a tree" problems reduce to: solve for the left subtree, solve for the right subtree, combine with the current node, return the result upward (postorder), optionally updating a global best along the way.

Why it works

The recursive definition guarantees structural induction: if an algorithm is correct on the empty tree and on a node given correct answers for both subtrees, it is correct on every finite binary tree.

Every traversal touches each node exactly once and each edge twice (down and up), so all traversals are O(n) time. Recursive DFS uses O(h) stack space; BFS uses O(w) queue space where w is the maximum level width (up to n/2).

Operations

OperationDescriptionCost
traverse (DFS)Visit every node in preorder, inorder or postorder using recursion or an explicit stack.O(n)
traverse (BFS)Visit nodes level by level using a queue.O(n)
heightLongest root-to-leaf path, computed postorder as 1 + max(height(left), height(right)).O(n)
searchFind a value; without ordering every node may need to be checked.O(n)
insertAttach a new node at a chosen empty slot (for level-order fill, at the first empty position found by BFS).O(n)
deleteRemove a node and reattach or replace its subtrees according to the tree's policy.O(n)

Recognition

How to tell a problem wants this.

  • The input is described as a tree, given as a root node, or a serialized level-order array like [3,9,20,null,null,15,7].
  • The question asks for depth, height, diameter, path sums, symmetry, lowest common ancestor, or "level order" output.
  • A problem about nested or hierarchical data (expressions, file systems, decision paths) with at most two options per step.
“minimum steps” → Breadth-First Search“connected groups” → Depth-First Search“binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

452731
inorder output
empty
1/27Start a inorder traversal at the root 1. The output list on the right fills as nodes are visited.
Node being processedOn the call stackAlready output
PseudocodeLearn Binary Tree →
1traverse(node):
2  if node is null: return
3  [preorder]  visit(node)
4  traverse(node.left)
5  [inorder]   visit(node)
6  traverse(node.right)
7  [postorder] visit(node)
8levelorder: queue = [root]
9  while queue: node = queue.popleft(); visit(node); push node.left, node.right
Variables
orderinorder
nodes6
Complexity
access O(n)
search O(n)
insert O(n)
delete O(n)
Speed

Pseudocode

1inorder(node):
2  if node is null: return
3  inorder(node.left)
4  visit(node)
5  inorder(node.right)
6levelOrder(root):
7  queue = [root]; while queue not empty:
8    for each node in current level: visit(node); push children

Implementation

1from collections import deque
2from typing import Optional
3 
4 
51 · Node definition
6class TreeNode:
7    def __init__(self, val: int) -> None:
8        self.val = val
9        self.left: Optional["TreeNode"] = None
10        self.right: Optional["TreeNode"] = None
11 
12 
13class BinaryTree:
14    def __init__(self) -> None:
15        self.root: Optional[TreeNode] = None
16 
172 · Level-order insert (first empty slot found by BFS)
18    def insert_level_order(self, val: int) -> None:
19        node = TreeNode(val)
20        if self.root is None:
21            self.root = node
22            return
23        q = deque([self.root])
24        while q:
25            cur = q.popleft()
26            if cur.left is None:
27                cur.left = node
28                return
29            if cur.right is None:
30                cur.right = node
31                return
32            q.append(cur.left)
33            q.append(cur.right)
34 
353 · Recursive DFS traversals (preorder / postorder)
36    def preorder(self) -> list[int]:
37        out: list[int] = []
38 
39        def go(n: Optional[TreeNode]) -> None:
40            if n is None:
41                return
42            out.append(n.val)
43            go(n.left)
44            go(n.right)
45 
46        go(self.root)
47        return out
48 
49    def postorder(self) -> list[int]:
50        out: list[int] = []
51 
52        def go(n: Optional[TreeNode]) -> None:
53            if n is None:
54                return
55            go(n.left)
56            go(n.right)
57            out.append(n.val)
58 
59        go(self.root)
60        return out
61 
624 · Iterative inorder with an explicit stack
63    def inorder(self) -> list[int]:
64        out: list[int] = []
65        stack: list[TreeNode] = []
66        cur = self.root
67        while cur or stack:
68            while cur:
69                stack.append(cur)
70                cur = cur.left
71            cur = stack.pop()
72            out.append(cur.val)
73            cur = cur.right
74        return out
75 
765 · BFS level order
77    def level_order(self) -> list[list[int]]:
78        if self.root is None:
79            return []
80        levels: list[list[int]] = []
81        q = deque([self.root])
82        while q:
83            level: list[int] = []
84            for _ in range(len(q)):
85                n = q.popleft()
86                level.append(n.val)
87                if n.left:
88                    q.append(n.left)
89                if n.right:
90                    q.append(n.right)
91            levels.append(level)
92        return levels
93 
946 · Height (postorder combine)
95    def height(self) -> int:
96        def go(n: Optional[TreeNode]) -> int:
97            if n is None:
98                return 0
99            return 1 + max(go(n.left), go(n.right))
100 
101        return go(self.root)
Walkthrough
  1. TreeNode stores val, left, right; the Optional["TreeNode"] string annotation is needed because the class is referenced inside its own body.
  2. insert_level_order uses collections.deque for O(1) popleft().
  3. Recursive traversals use a nested go closure that appends to out; Python closures can mutate the list without nonlocal.
  4. inorder is iterative with a list used as a stack; while cur or stack mirrors the classic algorithm.
  5. level_order iterates range(len(q)) to process exactly one level per outer iteration.
  6. height returns 0 for None and 1 + max(...) otherwise.
Complexity (this implementation)
time O(n) per traversal · space O(h) recursion / O(w) queue

Python's default recursion limit is 1000 frames; a skewed tree deeper than that raises RecursionError unless you use sys.setrecursionlimit or iterate.

Language notes
  • collections.deque.popleft() is O(1); list.pop(0) is O(n).
  • Use is None rather than truthiness for node checks to avoid surprises if a node class defines __len__ or __bool__.
  • Type hints with Optional[TreeNode] are documentation only; nothing is enforced at runtime.
  • Python has no tail-call optimisation, so deep recursion always consumes stack frames.
Common mistakes in this language
  • Using list.pop(0) for BFS, making level order quadratic.
  • Hitting RecursionError on deep trees; convert to the iterative form or raise the limit.
  • Using a mutable default argument like def go(n, out=[]), which persists between calls.
Language differences that matter here
  • Memory: C++ must free nodes (destructor or unique_ptr); JS/TS/Python are garbage collected.
  • Recursion limits: Python defaults to 1000 frames, JS/TS around 10k, C++ is bounded by the OS stack (~8 MB); iterative traversals are safest on skewed trees.
  • Queues: C++ has std::queue, Python has deque; JS/TS need an index pointer or level swap to avoid O(n) shift().
  • Null: C++ uses nullptr, JS/TS null, Python None; TS makes the union explicit in the type.

Complexity

OperationAverageWorstNote
AccessO(n)O(n)No index; must traverse.
SearchO(n)O(n)
InsertO(n)O(n)O(1) if the attachment point is known.
DeleteO(n)O(n)
UpdateO(n)O(n)O(1) once the node is found.
TraversalO(n)O(n)
HeightO(n)O(n)
SpaceO(n)Recursive traversal adds O(h) stack; BFS adds O(w) queue where w is the widest level.

Advantages & disadvantages

Advantages
  • Naturally models hierarchical data and recursive structure; algorithms are short and provably correct by induction.
  • Serves as the skeleton of Binary Search Tree, AVL Tree, Binary Heap, Segment Tree and expression trees.
  • Traversals are linear time and need only O(h) extra space with recursion.
Disadvantages
  • Without an ordering or balancing invariant, search is O(n) and the tree can degenerate into a linked list.
  • Pointer-based nodes have poor cache locality compared with arrays.
  • Deep recursion on a skewed tree of 10^5 nodes overflows the default stack in most languages; an explicit stack is then required.

Use cases

  • Expression trees in compilers and calculators (operators at internal nodes, operands at leaves).
  • Decision trees in machine learning and game trees in search.
  • Huffman coding trees (Huffman Coding) that map prefix-free codes to symbols.
  • Interview problems on structure: diameter, symmetry, path sums, serialization.
Use it when
  • Data is inherently hierarchical with at most two branches per node (expressions, decisions).
  • You need the recursive skeleton for a BST, heap, or segment tree.
  • The problem hands you a tree and asks a structural question (depth, paths, symmetry, LCA).
Avoid it when
  • You need fast lookup by key with no ordering constraint — use a Hash Map.
  • Nodes can have many children — use an N-ary Tree or an Adjacency List.
  • Data is flat and index-addressed — an Array is simpler and cache-friendly.

Alternatives

N-ary TreeBinary Search TreeAdjacency ListLinked List

Common mistakes

  • Confusing height (edges or nodes?) — pick one convention and state it; height(null) is 0 when counting nodes and -1 when counting edges.
  • Forgetting the null check as the base case, causing a null dereference at leaves.
  • Recursing on a skewed tree of 10^5 nodes and overflowing the call stack; convert to an iterative traversal.
  • Mutating a shared result list inside recursion without resetting it between calls.
  • Assuming inorder traversal yields sorted output for a plain binary tree — that only holds for a BST.

Interview patterns

  • Postorder "return info up, update global best" for diameter, maximum path sum and balanced-tree checks.
  • Level-order with per-level size for zigzag, right-side view and level averages.
  • Serialize/deserialize with preorder plus null markers.
  • Lowest common ancestor: return the node if found, otherwise whichever side found something; both sides non-null means the current node is the LCA.
  • Build a tree from preorder + inorder using a hash map of inorder indices.
Interview questions on this
Mock interviews

Interview problems

Binary Tree Level Order TraversalmediumLowest Common Ancestor of a Binary TreemediumBinary Tree Maximum Path SumhardSerialize and Deserialize Binary Treehard