AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Trees coding problems

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.

New to trees? Read the Binary Trees and Tree Traversals tutorial first.

155 problems · 43 easy · 92 medium · 20 hard · judged by hidden tests in 13 languages

155problems

43 easy

92 medium

20 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Binary Tree Inorder Traversal

How it works

Trees, step by step

Sorted order from a binary search tree, with in-order traversal

insert 5, 3, 8, 1, 4, 7, 9, 2 into a BST, then traverse in order

12345789outputemptycall stack: empty

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.

0:01 / 0:34Step 1 of 10
Transcript · 10 steps

Study plan

Learn trees in 8 days

14 of the 155 Trees problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 141 in the full list below are practice at your own pace. Then move on to Trie.

  1. Day 1

    about 1 h 15 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

  2. Day 2

    about 55 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 1 h 10 min

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

  6. Day 6

    about 50 min

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

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Trie

Trees Coding Problems: 155 Questions with Solutions

155 trees coding problems — 43 easy · 92 medium · 20 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 155
  • By difficulty: 43 easy · 92 medium · 20 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.

New to trees? Read the Binary Trees and Tree Traversals tutorial first.

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

14 of the 155 Trees problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 141 in the full list below are practice at your own pace. Then move on to Trie.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

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

Day 4

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

Day 5

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

Day 6

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

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

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

Easy (43)

Medium (92)

Hard (20)

Companies that ask trees problems

Next topic: Trie