Trees: Fundamentals, Operations & Complexity

Trees

Why This Matters

Trees are hierarchical data structures that model relationships like organizational charts, file systems, and decision trees. Unlike linear structures (arrays, linked lists), trees have a branching structure with a root node and child nodes.

This matters because trees enable efficient operations that would be slow with linear structures. Binary Search Trees (BST) provide O(log n) search, insertion, and deletion (when balanced). Trees are used in databases (B-trees for indexing), compilers (parse trees), operating systems (directory structures), and networking (routing trees).

In interviews, tree problems test your understanding of recursion, tree traversals, and your ability to work with hierarchical data. Many algorithm problems become tree problems when you recognize the underlying structure.

What Engineers Usually Get Wrong

Most engineers think "trees are just linked lists with multiple pointers." While that's true structurally, the real power comes from tree properties (like BST ordering) and traversal algorithms. Engineers often implement tree operations iteratively when recursion would be simpler and more elegant.

Engineers also confuse different tree types. A binary tree is just a tree where each node has at most 2 children. A Binary Search Tree (BST) is a binary tree with ordering property (left < node < right). Not all binary trees are BSTs.

Another common mistake is not handling edge cases. What if the tree is empty? What if there's only one node? What if the tree is unbalanced (degenerates to linked list)? These cases cause bugs and performance issues.

How This Breaks Systems in the Real World

A database was using a BST to index records. Initially, records were inserted in sorted order (1, 2, 3, 4, 5...). This created a degenerate tree (essentially a linked list). Search operations that should be O(log n) became O(n). The database became slow. The fix? Use a self-balancing tree (AVL, Red-Black) or randomize insertion order. The lesson? Unbalanced trees lose their performance benefits.

Another story: A service was traversing a tree to find a value. The tree had cycles (a node pointed back to an ancestor), but the code didn't check for cycles. The traversal entered an infinite loop, causing the service to hang. The fix? Maintain a visited set or ensure the tree structure prevents cycles (trees are acyclic by definition, but bugs can create cycles).

Tree Fundamentals

Terminology

• Node: Element in the tree containing data and references to children
• Root: Topmost node (no parent)
• Leaf: Node with no children
• Internal node: Node with at least one child
• Parent: Node that has children
• Child: Node that has a parent
• Sibling: Nodes with the same parent
• Depth: Number of edges from root to node
• Height: Maximum depth in tree
• Level: All nodes at same depth

Tree Structure

        A (root)
       / \
      B   C
     / \   \
    D   E   F (leaves)

Binary Tree

A binary tree is a tree where each node has at most 2 children (left and right).

Implementation

1class TreeNode {
2  val: number;
3  left: TreeNode | null = null;
4  right: TreeNode | null = null;
5
6  constructor(val: number) {
7    this.val = val;
8  }
9}
10
11class BinaryTree {
12  root: TreeNode | null = null;
13
14  // Insert (level-order, for complete binary tree)
15  insert(val: number): void {
16    const newNode = new TreeNodeval

Tree Traversals

Inorder (Left, Root, Right)

1function inorderTraversal(root: TreeNode | null): number[] {
2  const result: number[] = [];
3
4  function inorder(node: TreeNode | null): void {
5    if (!node) return;
6    inorder(node.left);   // Left
7    result.push(node.val); // Root
8    inorder(node.right);  // Right
9  }

Preorder (Root, Left, Right)

1function preorderTraversal(root: TreeNode | null): number[] {
2  const result: number[] = [];
3
4  function preorder(node: TreeNode | null): void {
5    if (!node) return;
6    result.push(node.val); // Root
7    preorder(node.left);   // Left
8    preorder(node.right);  // Right
9  }

Postorder (Left, Right, Root)

1function postorderTraversal(root: TreeNode | null): number[] {
2  const result: number[] = [];
3
4  function postorder(node: TreeNode | null): void {
5    if (!node) return;
6    postorder(node.left);   // Left
7    postorder(node.right);  // Right
8    result.push(node.val);  // Root
9  }

Level-Order (BFS)

1function levelOrder(root: TreeNode | null): number[][] {
2  if (!root) return [];
3
4  const result: number[][] = [];
5  const queue: TreeNode[] = [root];
6
7  while (queue.length > 0) {
8    const levelSize = queue.length;
9    const level: number[] = [

Binary Search Tree (BST)

A BST is a binary tree with ordering property:

• Left subtree contains values < node
• Right subtree contains values > node
• Both subtrees are also BSTs

Search

1function searchBST(root: TreeNode | null, val: number): TreeNode | null {
2  if (!root || root.val === val) return root;
3  
4  if (val < root.val) {
5    return searchBST(root.left, val);
6  } else {
7    return searchBST(root.right, val);
8  }
9}
10
11// Iterative
12function searchBSTIterative(root: TreeNode | null val  TreeNode

Insert

1function insertIntoBST(root: TreeNode | null, val: number): TreeNode {
2  if (!root) {
3    return new TreeNode(val);
4  }
5
6  if (val < root.val) {
7    root.left = insertIntoBST(root.left, val);
8  } else {
9    root.right = insertIntoBST(root.right, val);
10  }
11
12  return root;
13}

Delete

1function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
2  if (!root) return null;
3
4  if (key < root.val) {
5    root.left = deleteNode(root.left, key);
6  } else if (key > root.val) {
7    root.right = deleteNode(root.right, key);
8  } else {
9    // Node to delete found
10    if rootleft  rootright

Examples

Example 1: Maximum Depth

1function maxDepth(root: TreeNode | null): number {
2  if (!root) return 0;
3  
4  const leftDepth = maxDepth(root.left);
5  const rightDepth = maxDepth(root.right);
6  
7  return Math.max(leftDepth, rightDepth) + 1;
8}
9
10// Time: O(n) - visit each node once
11// Space: O(h) - recursion stack
12// Edge cases: empty tree, single node, unbalanced tree

Example 2: Validate BST

1function isValidBST(root: TreeNode | null): boolean {
2  function validate(
3    node: TreeNode | null,
4    min: number,
5    max: number
6  ): boolean {
7    if (!node) return true;
8    
9    if (node.val <= min || node.val >= max) {
10      return false;
11    }
12    
13    return (
14      validate(node.left, min, nodeval

Example 3: Lowest Common Ancestor (BST)

1function lowestCommonAncestor(
2  root: TreeNode | null,
3  p: TreeNode,
4  q: TreeNode
5): TreeNode | null {
6  if (!root) return null;
7
8  // Both in left subtree
9  if (p.val < root.val && q.val < root.val) {
10    return lowestCommonAncestor(root.left, p, q);
11  }
12  
13  // Both in right subtree
14  if (p.val > root.val && q.val > rootval

Example 4: Serialize and Deserialize Binary Tree

1function serialize(root: TreeNode | null): string {
2  const result: string[] = [];
3
4  function preorder(node: TreeNode | null): void {
5    if (!node) {
6      result.push('null');
7      return;
8    }
9    result.push(node.val.toString());
10    preorder(node.left);

Common Pitfalls

• Not handling null/empty tree: Always check if (!root) before operations
• Confusing binary tree with BST: Not all binary trees are BSTs. BST has ordering property
• Unbalanced trees: Degenerate trees (linked list) lose O(log n) benefits. Use self-balancing trees
• Incorrect traversal: Mixing up inorder, preorder, postorder causes wrong results
• Memory leaks: In languages without GC, ensure proper cleanup when deleting nodes
• Cycle detection: Trees are acyclic by definition, but bugs can create cycles
• Not updating parent pointers: When deleting nodes, ensure parent pointers are updated
• Off-by-one in depth/height: Depth is edges from root, height is max depth

Failure Stories You'll Recognize

The Unbalanced Tree: A database was using a BST to index records. Records were inserted in sorted order, creating a degenerate tree (linked list). Search operations became O(n) instead of O(log n). The database became slow. The fix? Use a self-balancing tree (AVL, Red-Black) or randomize insertion order. The lesson? Unbalanced trees lose performance benefits.

The Infinite Loop: A service was traversing a tree to find a value. Due to a bug, a node pointed back to an ancestor, creating a cycle. The traversal entered an infinite loop. The service hung. The fix? Maintain a visited set, or ensure tree structure prevents cycles (trees are acyclic by definition).

The Wrong Traversal: A service was using inorder traversal to copy a tree structure. But inorder doesn't preserve structure—it gives sorted order. The copied tree had wrong structure. The fix? Use preorder traversal to preserve structure. The lesson? Choose traversal based on what you need (structure vs order).

What Interviewers Are Really Testing

They want to see you understand tree properties and choose the right traversal. Junior engineers use the wrong traversal or don't handle edge cases. Senior engineers understand when to use each traversal and handle null/empty cases correctly.

When they ask "validate a BST," they're testing:

• Do you understand BST ordering property?
• Can you handle edge cases (empty tree, duplicates)?
• Do you use the right approach (bounds checking vs inorder)?

Interview Questions

Beginner

Q: What is the difference between a binary tree and a binary search tree?

A:

Binary Tree:

• Each node has at most 2 children
• No ordering constraint
• Used for hierarchical data, expression trees
• Search: O(n) - must check all nodes

Binary Search Tree (BST):

• Binary tree with ordering property
• Left subtree < node < right subtree
• Used for efficient search, insertion, deletion
• Search: O(log n) if balanced, O(n) if unbalanced

Key Difference:

• Binary Tree: Structure only (2 children max)
• BST: Structure + ordering property (enables efficient search)

Example:

Binary Tree (not BST):     BST:
      5                        5
     / \                      / \
    3   7                    3   7
   / \   \                  / \   \
  1   9   2                1   4   9

Intermediate

Q: How do you find the lowest common ancestor (LCA) of two nodes in a BST?

A:

Approach: Use BST property

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (!root) return null;

  // Both in left subtree - LCA is in left
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  
  // Both in right subtree - LCA is in right
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  
  // LCA found: p and q on different sides, or one is root
  return root;
}

// Iterative version
function lowestCommonAncestorIterative(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  let current = root;
  
  while (current) {
    if (p.val < current.val && q.val < current.val) {
      current = current.left;
    } else if (p.val > current.val && q.val > current.val) {
      current = current.right;
    } else {
      return current; // LCA found
    }
  }
  
  return null;
}

// Time: O(h) where h is height
// Space: O(1) iterative, O(h) recursive
// Edge cases: p or q not in tree, p equals q

How it works: Use BST property. If both nodes are smaller than root, LCA is in left subtree. If both are larger, LCA is in right subtree. Otherwise, root is LCA.

For regular binary tree (not BST), use different approach:

• Find paths from root to both nodes
• Find last common node in paths

Senior

Q: Design a data structure that supports insert, delete, search, and getRandom all in O(1) average time. How would you implement it using trees?

A:

Challenge: BST gives O(log n) operations, but we need O(1).

Solution: Use hash map + array (not tree-based), but if we must use tree structure, we can use a balanced BST with size tracking.

Better Solution (Hash Map + Array):

class RandomizedSet {
  private map: Map<number, number> = new Map(); // val -> index
  private arr: number[] = [];

  insert(val: number): boolean {
    if (this.map.has(val)) return false;
    
    this.arr.push(val);
    this.map.set(val, this.arr.length - 1);
    return true;
  }

  remove(val: number): boolean {
    if (!this.map.has(val)) return false;
    
    const index = this.map.get(val)!;
    const lastVal = this.arr[this.arr.length - 1];
    
    // Swap with last element
    this.arr[index] = lastVal;
    this.map.set(lastVal, index);
    
    // Remove last element
    this.arr.pop();
    this.map.delete(val);
    
    return true;
  }

  getRandom(): number {
    const randomIndex = Math.floor(Math.random() * this.arr.length);
    return this.arr[randomIndex];
  }

  search(val: number): boolean {
    return this.map.has(val);
  }
}

// Time: All operations O(1) average
// Space: O(n)

If tree structure required: Use balanced BST (Red-Black) with size tracking, but operations are O(log n), not O(1).

• Tree: Hierarchical structure with root and child nodes. Used for hierarchical data, efficient search
• Binary Tree: Each node has at most 2 children. No ordering constraint
• Binary Search Tree (BST): Binary tree with ordering (left < node < right). Enables O(log n) search if balanced
• Tree Traversals: Inorder (sorted for BST), Preorder (structure), Postorder (delete), Level-order (BFS)
• BST Operations: Search/Insert/Delete O(h) where h is height (O(log n) if balanced, O(n) if unbalanced)
• Balancing: Unbalanced trees degrade to O(n). Use self-balancing trees (AVL, Red-Black) for guaranteed O(log n)
• Common operations: Find depth, validate BST, find LCA, serialize/deserialize
• Edge cases: Empty tree, single node, unbalanced tree, duplicate values
• Use cases: Databases (B-trees), compilers (parse trees), file systems, expression evaluation
• Recursion: Tree problems often use recursion naturally. Understand base case (null node) and recursive case

How InterviewCrafted Will Teach This

We'll teach trees through traversal problems and BST operations, not abstract definitions. Instead of memorizing "a tree has nodes and edges," you'll learn through scenarios like "how do you validate a BST?" or "how do you find the lowest common ancestor?"

You'll see how trees are used in real systems (database indexes, file systems) and understand when to use trees vs other structures. When an interviewer asks "validate a BST," you'll think about ordering properties and bounds checking—not just "check left < node < right."

• Linked Lists - Trees are built using nodes with pointers (similar to linked lists). Understanding pointers helps with tree operations.
• Recursion & Backtracking - Tree traversals and operations are naturally recursive. Understanding recursion is essential for tree algorithms.
• Stacks and Queues - Iterative tree traversals use stacks (DFS) and queues (BFS). Understanding these helps with non-recursive tree algorithms.
• Graphs - Trees are a special type of graph (acyclic, connected). Understanding trees helps with graph algorithms.
• Self-Balancing Trees - AVL and Red-Black trees extend BST concepts with automatic balancing. Understanding BSTs is prerequisite for self-balancing trees.
• B-Trees - Multi-way trees used in databases. Understanding binary trees helps understand B-tree concepts.