Get started

Trees Coding Problems: 5 Questions with Solutions

5 trees coding problems — 4 medium · 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 4-day plan.

  • Problems: 5
  • By difficulty: 4 medium · 1 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A tree is a connected graph with no cycles: n nodes joined by exactly n − 1 edges, with one path between any two of them. Pick a root and every other node gets a parent, a depth and a subtree of its own — the shape of an organisation chart, a road network leading to a capital, a directory listing. The problems here give the tree as an edge list or a parent array rather than as linked nodes, and practise rooting it, walking it without stepping back to the parent, and building each node's answer from its children's.

How trees works, step by step

12345789output12345789call stack: empty
Sorted order from a binary search tree, with in-order traversal. Example: insert 5, 3, 8, 1, 4, 7, 9, 2 into a BST, then traverse in order
  1. In a binary search tree every value in a node's left subtree is smaller and every value in its right subtree is larger. In-order traversal visits left subtree, node, right subtree, so it should write the values out in sorted order.
  2. The calls go left from the root as far as they can: 5 → 3 → 1. 1 has no left child, so it is written first, the smallest value; then the traversal moves into its right subtree at 2.
  3. 2 has no left child, so it is written next; with no right child, the calls unwind to 3, which was waiting for its left side.
  4. 3's left subtree (1 and 2) is finished, so 3 is written next; then the traversal moves into its right subtree at 4.
  5. 4 has no left child, so it is written next; with no right child, the calls unwind to 5, which was waiting for its left side.
  6. 5's left subtree (1, 2, 3 and 4) is finished, so 5 is written next; then the traversal moves into its right subtree at 8.
  7. 7 has no left child, so it is written next; with no right child, the calls unwind to 8, which was waiting for its left side.
  8. 8's left subtree (7) is finished, so 8 is written next; then the traversal moves into its right subtree at 9.
  9. 9 has no left child, so it is written next; with no right child and no call waiting, the traversal is over.
  10. The output [1, 2, 3, 4, 5, 7, 8, 9] is sorted, because each node was written after everything smaller than it (its left subtree) and before everything larger. Each node is visited once: O(n) time, with a call stack no deeper than the tree's height.

Trees study plan

All 5 Trees problems (4 medium and 1 hard) over 4 days, about 3 h 25 min in all — the pattern first, then easiest to hardest. Then move on to Trie.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Next topic: Trie

Trees: the essentials

When to reach for it

"n nodes and n − 1 edges", "rooted at node 0", "manager[i] is the manager of i", "the subtree of node i". With one path between any two nodes there is no route to choose and nothing to mark visited but the parent. Most questions are a value flowing down from the root (an arrival time, a depth) or a summary flowing up from the leaves (a subtree's size or label counts).

The pattern

Build an adjacency list and run a Depth-First Search from the root, passing the parent so the walk never climbs back up. Values flowing down travel as arguments; values flowing up are combined after the children return.

def subtree_sizes(n, edges):            # tree rooted at node 0
    adj, size = [[] for _ in range(n)], [1] * n
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    def walk(u, parent):
        for v in adj[u]:
            if v != parent:             # never back up the edge just used
                walk(v, u)
                size[u] += size[v]      # v's subtree is complete by now
    walk(0, -1)
    return size

Cost

O(n) time and space, since a tree has n − 1 edges. The recursion is as deep as the tree is tall, n − 1 for a path. A parent array is the same tree: u's children are the i with parent[i] == u.

Common mistakes

  • Walking back to the parent: each undirected edge is stored both ways, so the recursion never ends.
  • Recursing 10⁵ levels in Python (default limit 1,000 frames); process a breadth-first order in reverse instead, children before parents.
  • Assuming an edge [u, v] names the parent first; root the tree yourself.
  • Forgetting the one-node tree, whose edge list is empty.

Start with

All trees problems

Medium (4)

Hard (1)

Companies that ask trees problems

Next topic: Trie