Binary trees and BSTs: traversals and interview patterns

A tree is a hierarchy of nodes. A binary tree has at most two children per node (left and right). The top node is the root, nodes without children are leaves, and the height is the longest path from the root to a leaf.

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

Binary search tree (BST)

A BST adds an ordering rule: for every node, values in the left subtree are smaller and values in the right subtree are larger.

• Search, insert and delete take O(h), where h is the height.
• If the tree is balanced, h is about log n, so operations are O(log n).
• If it is badly unbalanced (for example inserting sorted values), it degrades to a list with O(n). Self-balancing trees (AVL, red-black) prevent this.
• An inorder traversal of a BST visits values in sorted order. This fact solves many problems.

The four traversals

Depth-first (DFS), three orders depending on when you visit the node:

function preorder(n)  { if (!n) return; visit(n); preorder(n.left);  preorder(n.right); }  // node, left, right
function inorder(n)   { if (!n) return; inorder(n.left);  visit(n);  inorder(n.right); }   // left, node, right
function postorder(n) { if (!n) return; postorder(n.left); postorder(n.right); visit(n); } // left, right, node

• Preorder: copy or serialise a tree (parents before children).
• Inorder: sorted order in a BST.
• Postorder: compute from the bottom up (children before the parent), such as height or deleting a tree.

Breadth-first (BFS), level order, using a queue:

function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const size = queue.length, level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();       // use a real queue for large trees
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}
// Time O(n), space O(width)

All traversals visit each node once: O(n) time. DFS recursion uses O(h) stack space.

Recursive thinking on trees

Most tree problems use this pattern: solve for the left, solve for the right, combine at the node, with a base case for null.

Height:

const height = (n) => (n ? 1 + Math.max(height(n.left), height(n.right)) : 0);

Same tree, invert tree, symmetric tree, path sum: all follow the same shape.

Diameter (longest path between two nodes): at each node the path through it is left height plus right height. Track the best value while computing heights, in one pass.

Lowest common ancestor (LCA):

• In a general binary tree: if the current node is one of the targets, return it. Recurse both sides. If both sides return a node, the current node is the LCA.
• In a BST: use the ordering. If both targets are smaller, go left. If both larger, go right. Otherwise the current node is the LCA.

Validating a BST (a classic trap)

Checking only that each node is larger than its left child and smaller than its right child is wrong. A value deep in the left subtree could still exceed an ancestor. Pass down the valid range:

function isValidBST(node, lo = -Infinity, hi = Infinity) {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  return isValidBST(node.left, lo, node.val) && isValidBST(node.right, node.val, hi);
}

Alternatively, do an inorder traversal and check that values strictly increase.

Other patterns

• Kth smallest in a BST: inorder traversal, stop at k.
• Build a tree from preorder and inorder arrays: the first preorder value is the root; find it in inorder to split left and right.
• Serialise and deserialise a tree: preorder with null markers.
• Binary tree right-side view: last node of each level in BFS.
• Trie, heap and segment tree are other tree-shaped structures that appear in harder problems.

Complexity and space

• Time is usually O(n), because each node is visited once.
• Space is O(h) for DFS recursion (O(log n) balanced, O(n) worst case) and O(w) for BFS, where w is the maximum width.
• A skewed tree can make recursion very deep. Mention an iterative approach with an explicit stack if depth could be huge.

Common mistakes

• Forgetting the null base case.
• Confusing a BST with a general binary tree and using ordering where it does not exist.
• The BST validation trap above.
• Mutating shared lists in recursion (copy paths before storing them).
• Using shift() on a large array as a queue, which is slow.

Practice problems

Maximum Depth, Invert Binary Tree, Same Tree, Symmetric Tree, Level Order Traversal, Validate BST, Lowest Common Ancestor, Kth Smallest in BST, Diameter of Binary Tree, Construct Tree from Preorder and Inorder.

Takeaway: know the four traversals, think "left, right, combine" with a null base case, use the sorted-inorder property of BSTs, and validate BSTs with ranges.

---

Interview prep and DSA series, Part 2 (data structures and behaviour): 2 of 5. Previous: Linked lists, stacks and queues: patterns for interviews.