All Roadmaps›🧠 Data Structures & Algorithms›Phase 4›Binary Trees — Traversals & Core Operations

Binary Trees — Traversals & Core Operations

0/12 in this phase0/57 across the roadmap

📖 Concept

A binary tree is a hierarchical structure where each node has at most two children (left and right). Trees are the foundation for BSTs, heaps, tries, and many advanced structures.

Terminology:

  • Root: Top node (no parent)
  • Leaf: Bottom node (no children)
  • Height: Longest path from root to leaf
  • Depth: Distance from root to a node
  • Balanced: Height difference between left and right subtrees ≤ 1

Traversals (DFS):

  1. Inorder (Left, Root, Right) — gives sorted order for BST
  2. Preorder (Root, Left, Right) — used for serialization
  3. Postorder (Left, Right, Root) — used for deletion

Traversals (BFS):

  • Level-order — visit all nodes at depth d before depth d+1

Key properties:

  • Max nodes at level i: 2ⁱ
  • Max total nodes of height h: 2^(h+1) - 1
  • Height of balanced tree with n nodes: O(log n)
  • Height of skewed tree: O(n)

🏠 Real-world analogy: Family tree. You (root) have two children. Each child has two children. To find someone: inorder is alphabetical, preorder answers "who's the boss?", postorder answers "who finishes last?"

💻 Code Example

codeTap to expand ⛶
1// TREE NODE
2class TreeNode {
3  constructor(val, left = null, right = null) {
4    this.val = val;
5    this.left = left;
6    this.right = right;
7  }
8}
9

10// THREE DFS TRAVERSALS — Recursive
11function inorder(root, result = []) {
12  if (!root) return result;
13  inorder(root.left, result);
14  result.push(root.val);     // Left → ROOT → Right
15  inorder(root.right, result);
16  return result;
17}
18

19function preorder(root, result = []) {
20  if (!root) return result;
21  result.push(root.val);     // ROOT → Left → Right
22  preorder(root.left, result);
23  preorder(root.right, result);
24  return result;
25}
26

27function postorder(root, result = []) {
28  if (!root) return result;
29  postorder(root.left, result);
30  postorder(root.right, result);
31  result.push(root.val);     // Left → Right → ROOT
32  return result;
33}
34

35// LEVEL ORDER (BFS)
36function levelOrder(root) {
37  if (!root) return [];
38  const result = [], queue = [root];
39  while (queue.length) {
40    const level = [], size = queue.length;
41    for (let i = 0; i < size; i++) {
42      const node = queue.shift();
43      level.push(node.val);
44      if (node.left) queue.push(node.left);
45      if (node.right) queue.push(node.right);
46    }
47    result.push(level);
48  }
49  return result;
50}
51

52// MAX DEPTH
53function maxDepth(root) {
54  if (!root) return 0;
55  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
56}
57

58// IS BALANCED
59function isBalanced(root) {
60  function height(node) {
61    if (!node) return 0;
62    const left = height(node.left);
63    if (left === -1) return -1;
64    const right = height(node.right);
65    if (right === -1) return -1;
66    if (Math.abs(left - right) > 1) return -1;
67    return 1 + Math.max(left, right);
68  }
69  return height(root) !== -1;
70}
71

72// IS SYMMETRIC
73function isSymmetric(root) {
74  function mirror(a, b) {
75    if (!a && !b) return true;
76    if (!a || !b) return false;
77    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
78  }
79  return mirror(root?.left, root?.right);
80}
81

82// DIAMETER OF BINARY TREE
83function diameterOfBinaryTree(root) {
84  let diameter = 0;
85  function depth(node) {
86    if (!node) return 0;
87    const left = depth(node.left);
88    const right = depth(node.right);
89    diameter = Math.max(diameter, left + right);
90    return 1 + Math.max(left, right);
91  }
92  depth(root);
93  return diameter;
94}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Implement all three DFS traversals (recursive and iterative)
  2. Level-order traversal
  3. Maximum depth of a binary tree
  4. Check if a binary tree is balanced
  5. Check if a binary tree is symmetric
  6. Invert a binary tree (mirror)
  7. Find the diameter of a binary tree
  8. Path sum — does a root-to-leaf path sum to target?
  9. Lowest common ancestor of two nodes
  10. Serialize and deserialize a binary tree

⚠️ Common Mistakes

  • Confusing height (root to leaf) with depth (root to node) — they go in opposite directions

  • Not handling the null case — every tree recursion must check if root is null

  • Using BFS when DFS is more natural (or vice versa) — depth questions → DFS, level questions → BFS

  • Forgetting that inorder of BST gives sorted order — many BST problems reduce to inorder traversal

  • Modifying tree during traversal without intention — clone first if the original must be preserved

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Binary Trees — Traversals & Core Operations

← PreviousAdvanced Recursion (Tree Recursion, Tail Call Optimization)Next →Binary Search Trees (BST) — Build, Search, Balance