ReviseAlgo Logo

Pattern Recognition Center

Decision Trees

Master pattern matching using keyword-based decision trees and algorithmic mapping stencils.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Pattern Decision Trees?

A Pattern Decision Tree is a logical flowchart that translates problem statements and keywords into specific algorithms. Instead of relying on intuition, you follow a structured set of queries regarding the problem's inputs and goals to find the optimal pattern.

Why study them?

Coding interview problems are deliberately worded to test your pattern matching skills. Recognizing standard keywords (such as "contiguous subarray" or "k-th largest") acts as an algorithmic compass, pointing you directly to the correct approach.

2. Mental Model: The Decision Path

Imagine playing the game 20 Questions:

  • You guess an object by asking yes/no questions (e.g. "Is it alive?", "Does it fly?").
  • Each answer eliminates thousands of possibilities.
  • An interview problem works the same way:
    • - "Is the input array sorted?" -> Yes? Think Binary Search or Two Pointers. No? Think Sorting or Heaps. - "Are we looking for a contiguous subarray?" -> Yes? Think Sliding Window or Prefix Sum.

    3. Keyword-to-Pattern Mapping Index

    Use this checklist to translate interview questions into coding patterns:

    1. Array & String Problems

  • "Contiguous subarray" + "target sum" \implies Sliding Window (for positive numbers) or Prefix Sum + HashMap (for negative numbers).
  • "Subarray" + "minimum/maximum value" \implies Monotonic Stack / Queue or Segment Trees.
  • "Sorted array" + "find target pair" \implies Two Pointers (converging left/right pointers).
  • "K-th largest / smallest element" \implies Min-Heap / Max-Heap or Quick Select.
  • "Subsets / Permutations" \implies Recursive Backtracking or Bitmasking.

    • 2. Graph & Tree Problems

  • "Shortest path in unweighted grid/graph" \implies BFS (queue level-order).
  • "Shortest path in weighted graph" \implies Dijkstra's algorithm (priority queue).
  • "Detect cycle / check connectivity" \implies Disjoint Set Union (DSU) or DFS.
  • "Dependency ordering / execution sequence" \implies Topological Sort (Kahn's indegree BFS).

    • 4. Visualizing the Decision Tree Flow

    5. Real-World Examples

  • Search Engine Parsing: Mapping query phrases dynamically to indexing databases.
  • Dependency Resolvers: Checking package compile tracks using topological sorts.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test mapping assumptions:
  • "Why use Sliding Window over Prefix Sum?" -> Sliding window is ideal for contiguous arrays with non-negative constraints because the window size increases or decreases monotonically. If the input contains negative numbers, window boundaries lose monotonicity, requiring a Prefix Sum + HashMap approach.
  • "When does Topological Sort fail?" -> It fails if the graph is not a Directed Acyclic Graph (DAG) (i.e. it contains a cycle). Always check for cycle conflicts by comparing sorted node counts to total graph vertices.

    • Common Mistakes

    Warning: 1. Using Dijkstra on Unweighted Graphs: Implementing Dijkstra (O(E log V)) to find shortest paths in unweighted grids instead of BFS (O(V + E)). This is unnecessarily slow and complex.
    > 2. Wrong Heap Selection: Using a Max-Heap to find the "K-th largest" elements instead of a Min-Heap. A Min-Heap keeps the largest elements at the bottom, allowing you to easily pop the smallest ones off the top in O(N log K) time.

    7. Summary

  • Contiguous Array: Sliding Window (positives) or Prefix Sum (negatives).
  • K-th element: Heap / Priority Queue.
  • Shortest Path: BFS (unweighted) or Dijkstra (weighted).
  • Subsets / Combinations: Backtracking.

    • 8. Quiz

    Question 1: If an array contains negative numbers and we need to find a subarray summing to K, what pattern should we use? Answer: Prefix Sum + HashMap. Sliding window fails here because negative numbers break the assumption that expanding the window increases the sum.
    Question 2: What pattern should be used to find the 'Top K frequent' words in a text stream? Answer: HashMap (for counting frequencies) followed by a Min-Heap of size K (to track the top K elements).
    Question 3: If you need to find dependency ordering in a compilation list, what algorithm is used? Answer: Topological Sort (implemented via Kahn's indegree BFS or DFS).
    Question 4: True or False: Binary search can only be applied to sorted arrays. Answer: False. It can also be applied to monotonic functions or search-on-answer ranges (e.g. finding the minimum capacity that makes a task feasible).
    Question 5: What is the optimal time complexity to find the K-th largest element in an unsorted array of size N? Answer: O(N) average time, using the Quick Select algorithm.