Skip to content
Tutorials Center
My learning

Topics

Lesson 221 of 225 ยท Practice and Review

Practice Problems: Trees, Graphs and DP

Twelve graded problems on trees, graphs and dynamic programming, from tree depth to Word Ladder and LCS. Each has a hint, a brute force, a solution and tests.

The first practice set covered arrays, strings and hashing. This one moves to the structures that interviews and real programs use when data has shape: trees, graphs and overlapping subproblems. The twelve problems go from easy to hard and follow the same routine: read the statement, think of the brute force, read the hint only if you need it, then compare with a complete solution that includes tests.

Where it is practical, the solution is checked against a slow, obviously correct version on random inputs. That habit, differential testing, is worth copying in your own practice: it finds the bugs that hand-picked examples miss.

For tree problems ask: what does each subtree need to tell its parent? For graph problems ask: what are the nodes, what are the edges, and is it weighted? For DP problems ask: what is the smallest version of this question, and how do bigger ones build on it?

All tree problems use this node class and a helper that builds a tree from a level-order list, where None marks a missing child (the same layout most interview sites use). The helper is repeated in each solution so every example runs on its own.

TEXT
build_tree([3, 9, 20, None, None, 15, 7])

        3
       / \
      9   20
         /  \
        15   7

Problem 1: Maximum Depth of a Binary Tree (easy)

Return the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.

Hint. The depth of a tree is 1 plus the larger of the depths of its two subtrees. What is the depth of an empty subtree?

Python Solution 1: recursion and BFS

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.

Time O(n), space O(h) for the recursion where h is the height (up to n for a chain). The BFS version counts levels and avoids deep recursion. See binary trees and level-order traversal.

Problem 2: Validate a Binary Search Tree (medium)

Decide whether a binary tree is a valid BST: every value in a node's left subtree is smaller than the node, every value in its right subtree is larger.

Hint. Checking only "left child < node < right child" is a classic trap. A value deep in the right subtree must also be larger than every ancestor it sits to the right of. Pass the allowed (low, high) range down the recursion.

Python Solution 2: carry bounds down

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 line deep violation shows the trap: 3 is a perfectly good left child of 6, so the naive check passes, yet 3 sits in the right subtree of 5 and is smaller than 5. Time O(n), space O(h). An in-order traversal of a valid BST must be strictly increasing, which gives a second solution; see binary search trees.

Problem 3: Lowest Common Ancestor (medium)

Given a binary tree and two values p and q that exist in it, return the value of their lowest common ancestor: the deepest node that has both as descendants (a node counts as a descendant of itself).

Hint. Recurse into both subtrees. If a call finds p or q it returns that node. If both the left and right calls return something, the current node is where the paths split.

Python Solution 3: post-order search

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.

Time O(n), space O(h). The case (5, 4) returns 5: a node is its own descendant. See tree problems. If the tree were a BST, you could walk down from the root in O(h) using the ordering instead.

Problem 4: Level Order and Right Side View (medium)

Return the node values level by level, top to bottom. Then use it to answer: which nodes would you see if you stood on the right side of the tree?

Hint. BFS with a queue; at the start of each level, note how many nodes the queue holds and process exactly that many.

Python Solution 4: BFS by levels

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.

In the second tree the deepest node 4 is on the left, but it is still visible from the right because nothing hides it at its level. Time O(n), space O(w) for the widest level.

Problem 5: Maximum Path Sum (hard)

A path is any sequence of connected nodes going up and down the tree, using each node at most once (it does not have to pass through the root). Return the maximum sum of node values on a path with at least one node. Values may be negative.

Hint. For each node, a path can bend there: its value plus the best downward path from the left plus the best downward path from the right. But what a node reports to its parent can only go down one side. Ignore any child path whose sum is negative.

Python Solution 5: post-order with a global best

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.

Check the first answer by hand: 15 + 20 + 7 = 42, a path that bends at 20. Time O(n), space O(h). The all-negative cases matter: the answer is the least negative single node, which is why best starts at negative infinity and not 0.

Problem 6: Number of Islands (medium)

A grid of "1" (land) and "0" (water). Count the islands, where an island is a group of land cells connected up, down, left or right.

Hint. Scan the grid. Each time you meet unvisited land, you found a new island: flood-fill it (DFS or BFS) so its cells are not counted again.

Python Solution 6: flood fill

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 second grid has five islands because diagonal cells do not connect. Time O(rows * cols), space O(rows * cols). See connected components and flood fill.

Problem 7: Course Schedule (medium)

There are n courses numbered 0 to n - 1. A pair (a, b) means you must finish course b before course a. Can you finish every course? If so, give one valid order.

Hint. This is a dependency graph. Repeatedly take courses with no remaining prerequisites (in-degree 0). If you cannot take all of them, there is a cycle.

Python Solution 7: Kahn's algorithm

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.

Time O(V + E), space O(V + E). See topological sort. Note the ambiguity: a valid order is not unique, so tests should check validity (every prerequisite comes earlier), not one specific list.

Problem 8: Network Delay Time (medium)

A network has n nodes numbered 1 to n. Each directed edge (u, v, w) means a signal takes w time to go from u to v. A signal starts at node k. How long until every node has received it? Return -1 if some node is unreachable.

Hint. Shortest paths with non-negative weights: Dijkstra. The answer is the largest of the shortest distances.

Python Solution 8: Dijkstra versus Bellman-Ford

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.

Time O(E log V), space O(V + E). Skipping already-finalised nodes (if node in dist) is the "lazy deletion" version of Dijkstra with heapq, which has no decrease-key. See Dijkstra and Bellman-Ford.

Problem 9: Word Ladder (hard)

Given a start word, an end word and a list of allowed words, find the number of words in the shortest sequence from start to end where each step changes exactly one letter and every word after the start is in the list. Return 0 if there is no sequence.

Hint. Words are nodes; one-letter differences are edges; fewest steps means BFS. Comparing every pair of words is slow. Group words by patterns with one wildcard, such as c*ld: words sharing a pattern are neighbours.

Python Solution 9: BFS with wildcard buckets

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.

With n words of length L, building the buckets costs O(n * L^2) (each pattern string costs O(L) to build) and BFS visits each word once. Comparing all pairs would be O(n^2 * L). See BFS.

Problem 10: House Robber (medium)

Houses on a street hold nums[i] money each. You cannot rob two adjacent houses. What is the maximum you can take?

Hint. Let best[i] be the most you can take from the first i houses. For house i you either skip it (best[i-1]) or rob it (best[i-2] + nums[i]).

Python Solution 10: DP with two variables

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 brute force tries all 2^n choices; the DP is O(n) time and O(1) space. The recurrence is the core of one-dimensional DP.

Problem 11: Coin Change, Counting the Ways (medium)

Given coin denominations (unlimited supply) and an amount, count the number of different combinations that make the amount. 1 + 2 and 2 + 1 are the same combination.

Hint. ways[a] is the number of combinations for amount a. Process coins one at a time (outer loop over coins, inner loop over amounts), so each combination is built in a fixed coin order. Swapping the loops counts ordered sequences instead.

Python Solution 11: combinations versus sequences

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.

Time O(len(coins) * amount), space O(amount). The two results for amount 5 (4 combinations, 9 ordered sequences) show how a loop order changes the meaning of the table. See coin change.

Problem 12: Longest Common Subsequence (medium)

Given two strings, find the length of their longest common subsequence (characters in order, not necessarily contiguous), and one such subsequence.

Hint. L[i][j] is the LCS length of the first i characters of a and the first j of b. If the last characters match, add 1 to L[i-1][j-1]; otherwise take the better of dropping one character from either string. Walk the table backwards to rebuild the string.

Python Solution 12: table and reconstruction

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.

Time and space O(len(a) * len(b)); if you only need the length, keep two rows for O(min(len(a), len(b))) space. The test checks three things: the length matches the brute force, the string has that length, and the string really is a subsequence of both inputs. See LCS and edit distance.

What to practise next

  • Redo the problems with a twist: the BST becomes an AVL tree; the grid has diagonal connections; the robber's street is circular.
  • Name the pattern before coding: depth-first return value, BFS by levels, topological order, shortest path, DP table. The cheat sheet lists the signals.
  • Time yourself against 25 minutes per medium problem, then review what slowed you down.
  • Finish the course with the interview questions.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does checking only "left child < node < right child" fail to validate a BST?

    A node deep in the right subtree must be larger than all ancestors it lies to the right of. Carrying (low, high) bounds down the recursion enforces this.
  2. 2. In Maximum Path Sum, why can a node report only one child path to its parent?

    A path is a simple chain. Passing both children's paths upward would make the path fork, which is not a path. Only at the bending point may it use both sides.
  3. 3. What does it mean when Kahn's algorithm outputs fewer nodes than the graph has?

    Nodes on a cycle never reach in-degree zero, so they are never added to the queue and are missing from the output.
  4. 4. In Coin Change (counting ways), what changes if the loops are swapped so the amount is the outer loop?

    With the amount outer, each amount considers every coin as the last one used, so different orders of the same coins are counted separately.
  5. 5. Which technique makes Word Ladder neighbour-finding efficient?

    Words that differ in exactly one position share a wildcard pattern, so they are found by a dictionary lookup instead of comparing all pairs.

Summary

  • Trees: let each subtree return the information its parent needs (depth, bounds, a path sum, a found node); BFS by levels for level-based questions.
  • Graphs: model nodes and edges first; use flood fill for components, Kahn's algorithm for ordering and cycles, Dijkstra for non-negative weights, BFS with buckets for word transformations.
  • DP: define the smallest subproblem, write the recurrence, and pick loop order carefully (combinations versus sequences).
  • Check every solution against a brute force on small random inputs, and test empty, single-element and impossible cases.
  • Many answers are not unique (orders, subsequences); test their properties, not one exact output.

Next: DSA Interview Questions and Answers