Binary Trees

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. The fixed limit of two children makes binary trees straightforward to implement — each node only needs two pointers — and enables algorithms that can efficiently narrow down a problem by going left or right at each step.

A useful intuition: think of a tournament bracket (each match has exactly one winner and one loser), a yes/no decision flowchart, or any process that repeatedly splits into exactly two possibilities. These real-world structures map naturally onto binary trees.

Binary Tree Node Structure#

Every node in a binary tree stores three pieces of information:

When a pointer is None (Python) or null (JavaScript), it means that child does not exist. A node with both pointers set to null is called a leaf node — it sits at the bottom of the tree with no descendants.

Types of Binary Trees#

Binary trees come in several variants, each with distinct structural guarantees and trade-offs. Recognizing which type you are working with tells you what operations are efficient and what assumptions you can safely make:

Tree Traversals#

Traversal means visiting every node in the tree exactly once, performing some action at each node (such as printing the value or accumulating a result). The order in which nodes are visited changes the meaning of the result, so choosing the right traversal is just as important as writing the traversal correctly. For binary trees, there are four primary strategies:

Inorder Traversal (Left, Root, Right)#

Inorder traversal follows the pattern Left → Root → Right: descend into the left subtree, process the current node, then descend into the right subtree. Its most important property is that when applied to a Binary Search Tree (BST), it visits every node in ascending sorted order. BSTs are covered in the next chapter — for now, just remember that inorder is the traversal to reach for when you need sorted output from a BST.

Preorder Traversal (Root, Left, Right)#

Preorder traversal follows the pattern Root → Left → Right: process the current node first, then descend into the left subtree, then the right subtree. Because each node is recorded before its children, preorder captures the parent-before-child relationship of the tree. This makes it well-suited for serializing a tree (encoding it as a flat sequence that can be fully reconstructed later) and for copying a tree (you must create the root before you can attach children to it).

Postorder Traversal (Left, Right, Root)#

Postorder traversal follows the pattern Left → Right → Root: fully process both subtrees before handling the current node. Because a node is only visited after all of its descendants have been processed, postorder is the correct choice when a parent depends on the results of its children. The two classic examples are deleting a tree (you must free the children before freeing the parent, otherwise you lose access to them) and evaluating an expression tree (you must evaluate the sub-expressions before you can apply the operator at the parent node).

Level-Order Traversal (BFS)#

Level-order traversal visits nodes level by level — all nodes at depth 0 first, then all at depth 1, and so on — processing nodes left to right within each level. This is also called Breadth-First Search (BFS) on the tree. It uses a queue (first-in, first-out) rather than a stack, because we want to process nodes in the same order they were discovered. A stack would reverse that order, which is exactly what we do not want here.

Traversal Comparison#

All four traversal strategies visit every node in O(n) time. What differs is the order — which determines what the resulting sequence means and which problems each traversal is naturally suited for:

Calculate Tree Height#

There are two common conventions for measuring tree height:

• Edge-based: count the number of edges on the longest root-to-leaf path. An empty tree has height -1; a single-node tree has height 0.
• Node-based: count the number of nodes on the longest root-to-leaf path. An empty tree has height 0; a single-node tree has height 1.

Both conventions are correct — they are off by one from each other. The implementations below show both. Be consistent within your own code, and check which convention a coding problem or interview expects.

Common Operations#

Applications of Binary Trees#

Reviewing AI-Generated Code#

Binary tree traversals are deceptively easy to get wrong — a single misplaced line silently produces incorrect output without raising an error. When reviewing AI-generated tree code, focus on two recurring failure points: the order in which nodes are visited, and how the underlying stack or queue is managed in iterative versions.

Questions to Ask When Reviewing Binary Tree Code#

1. "When exactly is the node visited?" — Confirm that the value is appended (or processed) at precisely the right point relative to the recursive calls, matching the intended traversal order.
2. "Show me the output for this small example tree" — Trace through a 3–7 node example by hand and compare it to the code's output. Discrepancies reveal order bugs instantly.
3. "In the iterative version, what is pushed to the stack first?" — Remember that a stack is LIFO: whatever is pushed last is processed first. Verify that the push order produces the intended visit order.
4. "What is the actual space complexity?" — Recursive solutions consume O(h) call-stack space, not O(1). For a skewed tree, that becomes O(n).

Summary#

Now that you understand binary trees and their traversals, continue to Binary Search Trees to see how adding a simple ordering rule — all left values smaller, all right values larger — transforms an ordinary binary tree into a structure that supports efficient searching, insertion, and deletion.