Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 77 ยท CS Fundamentals Interview Questions

Trees and Graphs Questions

Practice tree and graph interview questions: traversals, BST validation, lowest common ancestor, BFS, DFS, topological sort and shortest paths in Python.

Trees and graphs appear in almost every on-site loop because they test recursion, data-structure choice and careful bookkeeping at once. A tree is just a graph with no cycles and one parent per node, so the same ideas carry over. This lesson covers the questions you are most likely to meet, each with a runnable solution and its complexity.

Background: Tree traversals, Graph BFS, Graph DFS, Topological sort and Dijkstra.

Which traversal when?

DFS Go deep first. Recursion or a stack.
BFS Level by level. Uses a queue.
Shortest path BFS if unweighted, Dijkstra if weighted.
Ordering Topological sort for dependencies.
1 / 2

Tree traversals

Q: Name the traversals of a binary tree. Inorder visits left, node, right (for a BST this yields sorted order). Preorder visits node, left, right (useful to copy a tree). Postorder visits left, right, node (useful to delete or compute from children up). Level order visits one depth at a time with a queue. Each is O(n) time; space is O(h) for the recursion, or O(width) for level order.

Python Four traversals of one tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The for _ in range(len(queue)) trick processes exactly one level per outer iteration.

Validating a BST

Q: Is this tree a valid binary search tree? The common mistake is comparing each node only with its direct children. A node deep in the left subtree must still be smaller than the root. Pass down an allowed range (low, high) and tighten it as you descend. Alternatively, check that the inorder traversal is strictly increasing.

Python BST validation with ranges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bad tree passes a naive check, because 6 is greater than its parent 3. Only the range check notices that 6 must also be below 5.

Lowest common ancestor

Q: Find the lowest common ancestor (LCA) of two nodes. In a general binary tree, recurse: if the current node is one of the targets, return it; otherwise ask both subtrees. If both sides return something, the current node is the LCA. If only one does, pass that result up. This is O(n). In a BST you can do better: walk down from the root, and the first node whose value lies between the two targets is the LCA, in O(h).

Python LCA in a binary tree and in a BST

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BFS and DFS on graphs

Q: How do you traverse a graph? Store it as an adjacency list (a dictionary from node to its neighbors). Unlike a tree, a graph can have cycles, so keep a visited set. BFS uses a queue and explores in order of distance in edges, so it finds the shortest path in an unweighted graph. DFS uses recursion or a stack and is the tool for connectivity, cycle detection and path existence. Both cost O(V + E).

Python BFS shortest path and DFS reachability

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The parents dictionary does double duty: it is the visited set and it lets you rebuild the path.

Topological sort

Q: Given tasks and dependencies, find a valid order, or detect that none exists. Only a directed acyclic graph (DAG) has a valid order. Kahn's algorithm: count each node's incoming edges, start with the nodes that have none, and repeatedly remove one, lowering its neighbors' counts. If you finish with fewer nodes than the graph has, there is a cycle. Complexity O(V + E).

Python Kahn's algorithm with cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Shortest path with weights

Q: How do you find the cheapest route when edges have different costs? BFS counts edges, not cost, so it fails. Dijkstra keeps a min-heap of (distance, node) and always settles the closest unsettled node first. It requires non-negative weights; with negative edges use Bellman-Ford. Time is O((V + E) log V).

Python Dijkstra with heapq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The direct edge A -> B costs 4, but going through C costs 3. The if d > dist...: continue line skips stale heap entries.

Tree and graph classics: serialize, tree to list, width, cut vertices and spanning trees

The sections above cover traversals, BST validation, LCA, BFS/DFS and shortest paths. These are the next five questions that appear on "top 50" lists. Each one builds on a traversal you already know.

Serialize and deserialize a binary tree

Problem: turn a tree into a string and rebuild the identical tree from it.

A plain traversal is not enough, because the same preorder list fits many shapes. Write null markers for missing children and one traversal order is then unambiguous. Preorder with # for None is the easiest: read a value, then rebuild the left subtree, then the right. Both directions take O(n) time. Level-order (the format LeetCode shows) works too, using a queue.

Python Preorder with null markers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Convert a binary tree to a doubly linked list

Problem: rearrange the nodes so that left acts as prev and right as next, in inorder order, without allocating new nodes.

An inorder traversal visits nodes in sorted order for a BST. Keep a prev pointer to the node visited just before; at each node link prev.right = node and node.left = prev. O(n) time, O(h) stack space for tree height h.

Python Inorder threading into a doubly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Maximum width of a binary tree

Problem: the width of a level is the distance between its leftmost and rightmost non-null nodes, counting the nulls between them. Find the maximum.

Level-order BFS with a position index: give the root index 0, the left child 2*i and the right child 2*i + 1, as if the tree were a complete tree stored in an array. Width of a level is last_index - first_index + 1. Subtract the first index of the level before computing children (re-basing) so the numbers do not grow past what you can store in languages with fixed-size integers. Python integers do not overflow, but say it anyway.

Python Width with position indexes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Articulation points and bridges

Problem: an articulation point (cut vertex) is a vertex whose removal disconnects an undirected graph; a bridge is an edge with the same property. Find them in O(V + E).

Run one DFS and record two numbers per vertex: disc[v], the discovery time, and low[v], the earliest discovery time reachable from v's subtree using at most one back edge. For a tree edge u -> v:

  • the edge is a bridge if low[v] > disc[u] (the subtree of v cannot get back above u);
  • u is an articulation point if low[v] >= disc[u] and u is not the root, or if u is the root and has two or more DFS children.
Python Tarjan's low-link values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The parent check v == parent is fine for simple graphs. With parallel edges you must skip the parent edge by id instead of the parent vertex, otherwise a doubled edge is wrongly called a bridge.

Minimum spanning tree: Kruskal and Prim

Problem: connect all vertices of a weighted undirected graph with the least total edge weight.

Kruskal sorts all edges and adds each one that does not create a cycle, which it checks with a disjoint-set union (union-find). O(E log E). It is natural for an edge list and sparse graphs.

Prim grows one tree from a start vertex and always adds the cheapest edge leaving the tree, using a min-heap. O(E log V). It suits adjacency lists and dense graphs. Both are greedy, justified by the cut property: the lightest edge crossing any cut belongs to some MST. When edge weights are distinct the MST is unique, so both algorithms give the same total weight.

Python Kruskal with union-find, Prim with a heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the graph is disconnected, Kruskal returns a minimum spanning forest and Prim (from one start) covers only that component. Say so when asked about edge cases.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which traversal of a valid BST visits values in sorted order?

    Inorder visits left, node, right, and a BST keeps smaller values on the left.
  2. 2. Why is checking only node.left.val < node.val < node.right.val not enough to validate a BST?

    Every node in a left subtree must be smaller than all ancestors it lies to the left of, so you must carry a range down.
  3. 3. Which algorithm gives the shortest path by number of edges in an unweighted graph?

    BFS explores in layers of increasing distance, so the first time it reaches a node is by a shortest path.
  4. 4. Kahn's algorithm ends having output fewer nodes than the graph contains. What does that mean?

    Nodes in a cycle never reach in-degree zero, so they are never output.
  5. 5. Dijkstra's algorithm is not correct when the graph has:

    It assumes a settled node can never be improved, which a negative edge could break.

Summary

  • Know the four tree traversals and that inorder on a BST is sorted.
  • Validate a BST with a range passed down, not parent-only comparisons.
  • LCA: recurse and combine in a general tree, walk the values in a BST.
  • Graphs need a visited set; BFS for fewest edges, DFS for reachability, both O(V + E).
  • Topological sort (Kahn) orders a DAG and detects cycles; Dijkstra handles non-negative weights.
  • Serialize a tree with preorder plus null markers; thread an inorder walk into a doubly linked list with a prev pointer; BFS with position indexes gives the max width.
  • Cut vertices and bridges come from one DFS with discovery and low-link times; Kruskal (sort + union-find) and Prim (heap) both build a minimum spanning tree.

Next: Recursion and Dynamic Programming Questions.