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

1 

Tree Traversals

Inorder (Left, Root, Right)

1 

Preorder (Root, Left, Right)

1 

Postorder (Left, Right, Root)

1 

Level-Order (BFS)

1 

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

1 

Insert

1 

Delete

1 

Examples

Example 1: Maximum Depth

1 

Example 2: Validate BST

1 

Example 3: Lowest Common Ancestor (BST)

1 

Example 4: Serialize and Deserialize Binary Tree

1 

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).