Trees

Time Complexity

Key Points

• A node can have multiple children (general tree) or up to two children (binary tree)
• Tree questions often map to recursion with clear base and recursive steps
• Traversal order matters: inorder, preorder, postorder, and level-order
• Many tree problems are either "find/compare path", "measure property", or "transform tree"
• Height/diameter/path problems often combine DFS with state accumulation
• Binary search tree adds ordering: left < root < right
• Balance affects time complexity and recursion depth

Code Examples

function maxDepth(root) {
  if (!root) return 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}

function levelOrder(root) {
  if (!root) return []

  const result = []
  const queue = [root]

  while (queue.length > 0) {
    const levelSize = queue.length
    const level = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

function inorder(root, values = []) {
  if (!root) return values
  inorder(root.left, values)
  values.push(root.val)
  inorder(root.right, values)
  return values
}

Common Mistakes

• Forgetting base cases on null nodes in recursion
• Losing state in path problems (sum, distance, constraints)
• Mistaking node visit order (preorder/inorder/postorder)
• Confusing recursion state depth with global max values
• Ignoring height/width edge cases on empty and single-node trees
• Applying binary-search-tree assumptions to non-BST trees

Interview Tips

• Start with a DFS template before adding logic
• Use level-by-level reasoning for BFS questions
• Write examples manually before coding complex cases
• Track both return value and accumulator state in one pass when needed
• Talk complexity using n nodes and height h

Practice Problems

Related Concepts