🌱 Keegan's Digital Garden

04. Trees & Graphs

3 min read

Trees Graphs Trie (Prefix Tree) Priority Queue Tree Traversal DFS BFS

Clarify Tree Assumptions

  • Avoid making ambiguous assumptions about the tree type:
    • Tree vs. Binary Tree: A general tree may have any number of children, while a binary tree has at most two children per node.
    • Binary Tree vs. Binary Search Tree (BST): A BST enforces the left child < parent < right child property.
    • Balanced vs. Unbalanced Trees: Balanced trees (e.g., AVL, Red-Black) maintain height balance, while unbalanced trees may have large height differences.
    • Complete, Full, and Perfect Trees:
      • Complete: All levels filled except possibly the last, filled left to right.
      • Full: Every node has 0 or 2 children.
      • Perfect: All leaves are at the same level, and every internal node has 2 children.

Traversal Types

  • In-Order Traversal: Most common for BST-related problems (e.g., retrieving sorted values).
  • Pre-Order Traversal: Used for creating copies of a tree or for prefix expressions.
  • Post-Order Traversal: Common in problems requiring deletion of nodes or postfix expressions.
  • Level-Order Traversal (BFS): Used for tasks involving breadth-first exploration (e.g., finding the width of a tree).

Binary Heaps

  • Identifying Heap Questions:
    • Look for problems involving repeated min/max operations or priority queues.
  • Implementation Insights:
    • Binary heaps are often implemented as arrays.
    • Parent-child relationships:
      • Parent at i, children at 2i + 1 (left) and 2i + 2 (right).

Tries (Prefix Trees)

  • Key Properties:

    • A type of n-ary tree storing characters (1-26 for English alphabets).
    • Each path from the root to a node represents a prefix of a word.

  • Why Tries?

    • Unlike hash tables, tries efficiently check if a string is a valid prefix.
    • Used in problems requiring repeated prefix lookups (e.g., autocomplete, word search).

  • Common Use Cases:

    • Problems involving lists of valid words.
    • Searching through related prefixes repeatedly (e.g., “M”, “MA”, “MAN”, “MANY”).

Graphs: Key Insights

  • Preferred for visiting every node due to its simple implementation.
  • Suitable for problems like:
    • Detecting cycles.
    • Exploring all connected components.

  • Generally better for:

    • Finding the shortest path or any path between two nodes.
    • Level-order exploration of nodes.

  • Key Implementation Detail:

    • Use a queue to store nodes at the current level.

  • How It Works:

    • Runs two BFS searches, one from the source and one from the destination node.
    • The search completes when the paths from both searches meet.

  • Key Considerations:

    • Behavior differs on directed vs. undirected graphs.
    • Faster than traditional BFS in large graphs, as the search space grows slower with two simultaneous searches.

  • When to Use:

    • Use traditional BFS for single-direction traversal or when the graph is small.
    • Use bidirectional search when source and destination are well-defined, and the graph is large.

Graph View