DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Trees

A tree is a recursive data structure by definition — a node holding subtrees that are themselves trees — which is exactly why a recursive function that trusts its own calls on node.left and node.right tends to fall out naturally, mirroring the data's own shape.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function preorder(node, out = []) {
  if (!node) return out;             // base case: an empty subtree contributes nothing
  out.push(node.val);                // visit the ROOT first
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}

function inorder(node, out = []) {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.val);                // visit the root BETWEEN its two subtrees
  inorder(node.right, out);
  return out;
}

function postorder(node, out = []) {
  if (!node) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.val);                // visit the root LAST
  return out;
}

Each order fits a different job. Inorder traversal on a binary search tree visits values in fully sorted order — that single property is the entire reason a BST is useful for range queries and "give me things in order." Postorder is the natural shape for anything that must finish processing both children before touching the parent — computing subtree sizes or heights bottom-up, or safely deleting a tree node by node. Preorder is the natural shape for serializing or copying a tree, since visiting the root first means you can reconstruct the same structure by reading the output left to right.

Level-order traversal (BFS)

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];               // BFS uses a QUEUE, not a stack

  while (queue.length) {
    const levelSize = queue.length;   // snapshot: how many nodes belong to THIS level
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();     // dequeue from the front
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Worth flagging honestly: Array.prototype.shift() in JavaScript is O(n) per call, because removing the first element means re-indexing everything after it — so a naive JS BFS implemented this way is technically O(n²) on a wide tree or graph, even though the algorithm is conceptually O(n). A real deque, or shifting a read pointer across the array instead of physically removing elements, fixes the constant-factor issue; the pattern itself — snapshot the level size, drain exactly that many nodes, enqueue their children — is what actually matters for recognizing and writing the traversal correctly.

DFS — whether via recursion or an explicit stack — is the default choice for anything framed around a root-to-leaf path, or anything that naturally decomposes into "solve the left subtree, solve the right subtree, combine the two results." BFS is what you reach for the moment a question is explicitly about levels: "print each level," "find the minimum depth," "the closest node to the root satisfying some condition" — BFS finds it first, by construction, since it fully exhausts one level before touching the next.

Practice this on Code Lab: Trees and Depth-First Search