Skip to content

Trees and Graph cheatsheet

Question

In one short sentence each, define:

  • Tree DFS orders
  • BFS vs DFS
  • Graph representations
  • Trie
  • AVL
  • Dijkstra
  • A*

Solution

  • Tree DFS orders

    • Preorder = root-left-right
    • Inorder = left-root-right
    • Postorder = left-right-root

  • BFS vs DFS

    • BFS uses queue and gives shortest path in unweighted graph.
    • DFS uses stack/recursion and is better for structure/search/backtracking.

  • Graph representations

    • Adjacency list = default interview choice
    • Matrix = dense graphs, \(O(1)\) edge check
    • Objects/pointers = natural modeling

  • Trie

    • Prefix tree for strings; great for startswith.

  • AVL

    • Balanced BST with rotations and height tracking.

  • Dijkstra

    • Weighted shortest path, no negative edges.

  • A*

    • Dijkstra + heuristic; best for one target when heuristic is good.