Trees

A tree is a hierarchical data structure consisting of nodes connected by edges, with one node designated as the root. Each node can have zero or more children, and there are no cycles.

Key properties:

• Root: The topmost node with no parent
• Leaf: A node with no children
• Height: Longest path from root to any leaf
• Depth: Distance from root to a node
• Binary tree: Each node has at most 2 children (left and right)

Types of trees:

• Binary Tree: General tree with ≤2 children per node
• Binary Search Tree (BST): Left < parent < right
• Balanced trees: AVL, Red-Black (height ≈ log n)
• N-ary trees: Each node can have n children
• Trie: Tree for storing strings with shared prefixes

• Hierarchical relationships: File systems, organization charts, DOM, XML/JSON

  • Efficient operations: Search, insert, delete in O(log n) for balanced trees
  • Recursion practice: Trees are naturally recursive structures
  • Interview frequency: ~20% of coding interview problems involve trees

  Performance (balanced BST):

  • Search: O(log n)
  • Insert: O(log n)
  • Delete: O(log n)
  • Space: O(n)

  Traversal complexity:

  • DFS (all variants): O(n) time, O(h) space (h = height)
  • BFS: O(n) time, O(w) space (w = max width)

Use trees when you need:

1. Hierarchical data: Parent-child relationships, nested structures
2. Fast search: O(log n) lookup in balanced BST
3. Range queries: Find all elements in a range
4. Prefix matching: Trie for autocomplete, spell check
5. Expression evaluation: Parse trees for mathematical expressions

Common problem types:

• Tree traversals (preorder, inorder, postorder, level-order)
• Path problems (root-to-leaf, path sum, LCA)
• Tree construction (from traversals, from array)
• Tree modification (invert, flatten, serialize)
• BST operations (validate, kth smallest, insert/delete)
• Subtree problems (diameter, balanced check, subtree of another)

1. DFS (Depth-First Search) Explore as deep as possible before backtracking:

• Preorder: Root → Left → Right (copy tree, serialize)
• Inorder: Left → Root → Right (BST sorted order)
• Postorder: Left → Right → Root (delete tree, calculate height)

2. BFS (Breadth-First Search) Explore level by level using a queue:

• Level-order traversal
• Find shortest path in unweighted tree
• Zigzag traversal
• Right/left view of tree

3. Recursion patterns

• Top-down: Pass info from parent to children (path sum)
• Bottom-up: Compute from children, return to parent (height, diameter)
• Divide and conquer: Solve for left/right, combine results

4. BST properties

• Inorder traversal gives sorted order
• Left subtree < root < right subtree
• Can find kth smallest in O(h + k)

Path problems:

• Root-to-leaf paths with target sum
• Maximum path sum (can start/end anywhere)
• Lowest Common Ancestor (LCA)
• Distance between nodes

Tree construction:

• Build tree from preorder + inorder
• Build tree from postorder + inorder
• Construct BST from preorder

Tree modification:

• Invert/mirror tree
• Flatten to linked list
• Connect next pointers (level-order)
• Serialize and deserialize

Validation:

• Check if valid BST
• Check if balanced
• Check if symmetric
• Check if subtree of another tree

• Null pointer errors: Always check if node is null before accessing
  • Confusing preorder/inorder/postorder: Draw small examples to verify
  • Not handling edge cases: Empty tree, single node, skewed tree
  • Incorrect BST validation: Must check against range, not just parent
  • Modifying tree during traversal: Can cause unexpected behavior
  • Stack overflow: Deep recursion on skewed trees (use iterative or tail recursion)
  • Not considering duplicate values: BST may allow duplicates (left or right?)

1. Need sorted order? → Inorder traversal of BST
2. Level-by-level processing? → BFS with queue
3. Path from root to leaf? → DFS with path tracking
4. Need to modify tree? → Postorder (process children first)
5. Find/validate BST property? → Inorder or range validation
6. Lowest Common Ancestor? → Recursive search in both subtrees
7. Tree construction? → Identify root, split into left/right recursively
8. Serialize tree? → Preorder with null markers