DSA: Binary Trees

Understand binary tree structure, all traversal strategies, and classic tree algorithms like LCA, diameter, and tree views.

Tree Terminology

A tree is a hierarchical data structure. A binary tree is one where each node has at most two children, called the left child and the right child.

Key Tree Terms

Understanding these terms is essential before working with any tree algorithm.

  • Root: the topmost node with no parent
  • Leaf: a node with no children
  • Height: number of edges on the longest path from a node to a leaf (height of root = height of tree)
  • Depth / Level: number of edges from the root to the node (root is depth 0)
Tree TypeDefinition
Full Binary TreeEvery node has 0 or 2 children
Complete Binary TreeAll levels full except possibly the last, filled left to right
Perfect Binary TreeAll internal nodes have 2 children and all leaves are at the same level
Balanced Binary TreeHeight difference of left and right subtrees is at most 1 for every node

Binary Tree Representation

A binary tree node stores a value and two pointers: one to the left child and one to the right child. A null pointer means no child exists in that direction.

TreeNode Structure

Each node is a struct with val, left, and right. The tree is accessed through the root pointer alone.

  • Allocate each node on the heap with new
  • null left or right pointer indicates no child
  • A single root pointer is the only entry point to the whole tree
  • Memory usage: O(n) for n nodes, each holding two pointers

Building a Binary Tree

C++

Nodes are linked by assigning left and right pointers. The root pointer is the sole entry to the tree.

Tree Traversals: Inorder, Preorder, Postorder

The three depth-first traversals differ only in when the current node is visited relative to its left and right subtrees.

DFS Traversal Order

All three traversals visit every node exactly once in O(n) time with O(h) recursion stack space where h is the tree height.

  • Preorder: Root, Left, Right, useful for copying or serializing a tree
  • Inorder: Left, Root, Right, produces sorted output on a BST
  • Postorder: Left, Right, Root, useful for deleting a tree or evaluating expression trees
  • Recursive implementation is one or two lines per traversal

All Three DFS Traversals

C++

Only the position of the cout statement changes between the three traversal functions.

Iterative Inorder Traversal

The iterative version replaces the call stack with an explicit stack. It mirrors the recursive approach: go as far left as possible, process the node, then move to the right subtree.

Iterative Inorder with Explicit Stack

Push left children until null, then pop and process, then move to the right child and repeat.

  • Dive left: push every left child onto the stack
  • Pop when null is reached: this is the leftmost unprocessed node
  • Process the node, then set current to its right child
  • Continue until both the stack is empty and current is null

Iterative Inorder

C++

The explicit stack simulates the call stack. Diving left first, then processing on the way back up.

Height and Diameter of a Tree

The height of a tree is the number of edges on the longest root-to-leaf path. The diameter is the longest path between any two nodes in the tree, it may or may not pass through the root.

Computing Both in One Pass

Calculate height via postorder recursion. Track diameter as the maximum of (leftHeight + rightHeight) seen at any node.

  • Height of a null node = -1 (or 0 depending on the edge vs node convention)
  • Height of a node = 1 + max(leftHeight, rightHeight)
  • Diameter at a node = leftHeight + rightHeight + 2 (edge count through the node)
  • Pass diameter by reference so every recursive call can update the global maximum

Height and Diameter in One Postorder Pass

C++

Diameter at each node = lh + rh + 2. The global max across all nodes is the tree diameter.

Mirror and Symmetric Tree

Mirroring a tree swaps the left and right children at every node. A tree is symmetric if it is a mirror of itself, the left subtree mirrors the right subtree at every level.

Mirror and Symmetry Check

Mirror: swap left and right children recursively. Symmetric: compare the left subtree with the mirror image of the right subtree.

  • Mirror: swap(node->left, node->right) then recurse on both children
  • Symmetric: two-pointer recursive check, compare outer pair and inner pair simultaneously
  • Outer pair: left->left vs right->right
  • Inner pair: left->right vs right->left

Mirror and Symmetric Tree

C++

isSymmetric compares two subtrees simultaneously, checking that outer and inner pairs match.

Left View and Right View

The left view contains the first node visible at each level when looking from the left. The right view contains the last node visible at each level when looking from the right. Both are solved with level-order traversal.

Tree Views via Level Order

Process each level separately. The first node in a level is the left view; the last node is the right view.

  • Use a queue for BFS; snapshot the queue size at the start of each level
  • Left view: print the node when i == 0 (first in the level)
  • Right view: print the node when i == size - 1 (last in the level)
  • Alternatively, use DFS passing the current level and printing only on the first visit per level

Left and Right View per Level

C++

i == 0 captures the left view; i == sz-1 captures the right view within the same BFS loop.

Vertical Order Traversal

Assign a horizontal distance (HD) to each node: root = 0, left child = HD - 1, right child = HD + 1. Collect nodes column by column from the minimum to the maximum HD.

Horizontal Distance Mapping

A map keyed by horizontal distance groups nodes in the same vertical column. BFS ensures top-to-bottom order within each column.

  • BFS queue stores pairs of (node, horizontalDistance)
  • map<int, vector<int>> groups node values by HD
  • Iterate the map in key order (automatically sorted) to print columns left to right
  • Within the same HD and level, nodes appear left to right

Vertical Order Traversal

C++

BFS with HD tracking. std::map auto-sorts columns left to right by horizontal distance.

Lowest Common Ancestor (LCA)

The LCA of two nodes p and q is the deepest node that has both p and q as descendants. A single postorder traversal finds it in O(n) time.

LCA Recursive Strategy

If the current node equals p or q, return it. The LCA is the node where search results come back from both the left and right subtrees.

  • Base case: return node if node is null, p, or q
  • Recurse left and right and collect results
  • If both sides return non-null, the current node is the LCA
  • If only one side returns non-null, propagate that result upward

Lowest Common Ancestor

C++

When both recursive calls return non-null, the current node is exactly where the two paths meet.

Print All Root-to-Leaf Paths

Carry a running path vector during DFS. When a leaf is reached, the vector holds one complete root-to-leaf path. Backtrack by removing the current node before returning.

Path DFS with Backtracking

Push the current node's value before recursing, print at a leaf, then pop on the way back.

  • Push current value to path before recursing into children
  • Leaf check: node->left == null and node->right == null
  • Print the full path vector at every leaf
  • Pop the last element after both recursive calls return (backtrack)

All Root-to-Leaf Paths

C++

Backtracking via pop_back ensures the path vector accurately reflects the current DFS branch at all times.

Morris Inorder Traversal

Morris traversal performs inorder traversal in O(n) time and O(1) extra space by temporarily threading the right pointer of a node's inorder predecessor back to the current node.

Morris Threading Idea

Instead of a stack, create a temporary link from the inorder predecessor back to the current node so you can return to it after visiting the left subtree.

  • If current has no left child, print it and go right
  • Otherwise, find the inorder predecessor (rightmost node in the left subtree)
  • If predecessor right is null, thread it to current and go left
  • If predecessor right already points to current, remove the thread, print current, go right

Morris Inorder Traversal

C++

Threads are created and then destroyed in the same traversal. The tree is fully restored at the end.

Knowledge Check

1. The height of a binary tree with only the root node is:

2. Which traversal visits nodes in sorted order for a Binary Search Tree?

3. A complete binary tree is one where:

4. The diameter of a binary tree is defined as:

5. In preorder traversal, the visit order is:

6. The Lowest Common Ancestor (LCA) of two nodes p and q is:

7. Morris Inorder Traversal achieves O(n) time with:

8. Which traversal is used for level-order / BFS of a binary tree?

PreviousNext