Quartz 4

6.0 Trees and Binary Search

2 min read

Recursive hierarchical structures used in traversal-based problems, dynamic state management, and ordered data lookup. Binary Search leverages sorted structure or monotonic properties for O(log n) operations.

1.0 Tree Fundamentals and Traversals

  1. Inorder / Preorder / Postorder (recursive + iterative)
  2. Level-order (BFS using queue)
  3. DFS vs BFS trade-offs

2.0 Binary Search Tree (BST) Patterns

  1. Validate BST structure
  2. Floor / Ceiling / Closest value
  3. Kth smallest/largest element
  4. Range queries in BST

3.0 Binary Tree Recursion Patterns

  1. Subtree checking and symmetry
  2. Path sum variations (root-to-leaf, any-to-any)
  3. Diameter and max depth
  4. LCA (Lowest Common Ancestor)

4.0 Tree Construction and Serialization

  1. Build tree from inorder + preorder/postorder
  2. Serialize/deserialize binary trees (DFS/BFS)
  3. Flatten binary tree (in-place)

5.0 Binary Search Patterns (On Arrays)

  1. Standard binary search (left/right bounds)
  2. First/last occurrence (duplicates allowed)
  3. Search in rotated array
  4. Search on answer space (e.g., min capacity to ship packages)

6.0 Binary Search on Monotonic Functions

  1. Find smallest/largest x such that f(x) is valid
  2. Application in greedy/DP problems
  3. Lower bound / upper bound logic

7.0 Segment Trees and Advanced Structures

  1. Range query/update (RMQ, RSQ)
  2. Lazy propagation
  3. Binary Indexed Tree (Fenwick Tree)

8.0 N-ary Trees and Generalized Trees

  1. Generic tree traversal (DFS/BFS)
  2. M-ary trees, Trie basics
  3. Folder/tree structure parsing

9.0 Tree to Graph Transitions

  1. Convert tree to graph for bidirectional traversal
  2. BFS/DFS in tree-turned-undirected-graph

10.0 Special Mentions

  1. Morris Traversal (O(1) space inorder)
  2. Tree diameter via post-order
  3. Threaded trees
  4. Binary lifting (ancestor queries)
  5. Sparse tables

Graph View

Backlinks