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
insert 5, 3, 8, 1, 4, 7, 9, 2 into a BST, then traverse in order- 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.
- 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.
- 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.
- 3's left subtree (1 and 2) is finished, so 3 is written next; then the traversal moves into its right subtree at 4.
- 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.
- 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 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's left subtree (7) is finished, so 8 is written next; then the traversal moves into its right subtree at 9.
- 9 has no left child, so it is written next; with no right child and no call waiting, the traversal is over.
- 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.
- Binary Tree Inorder Traversal Easy
- Binary Tree Preorder Traversal Easy
- Binary Tree Postorder Traversal Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Same Tree Easy
- Reachable Nodes With Restrictions Medium
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.
- Number of Good Paths Hard
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.
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
- Reachable Nodes With Restrictions: one walk that refuses some nodes.
- Time Needed to Inform All Employees: a time passed down a manager array.
- Minimum Fuel Cost to Report to the Capital: subtree sizes decide the cars on each road.
All trees problems
Easy (43)
- Level of a Node in Binary Tree Breadth-First Search, Depth-First Search
- Sum of Leaf Nodes at Minimum Level Breadth-First Search
- Count BST Nodes That Lie in a Given Range Binary Search, Depth-First Search
- Nodes at Odd Levels Breadth-First Search
- Kth Largest Element in BST Depth-First Search, Stack
- Ceil in BST Binary Search
- Nodes at Distance K from Root Depth-First Search, Breadth-First Search
- Check if Two Trees are Isomorphic Depth-First Search, Recursion
- Check if All Leaves are at Same Level Depth-First Search, Breadth-First Search
- Children Sum in a Binary Tree Depth-First Search
- Transform to Sum Tree Depth-First Search, Recursion
- Left View of Binary Tree Breadth-First Search, Depth-First Search
- Count Complete Tree Nodes Binary Search, Bit Manipulation
- Convert Sorted Array to Binary Search Tree Array, Divide and Conquer
- Evaluate Boolean Binary Tree Depth-First Search
- Root Equals Sum of Children
- Sum of Root To Leaf Binary Numbers Depth-First Search, Bit Manipulation
- Cousins in Binary Tree Depth-First Search, Breadth-First Search
- Univalued Binary Tree Depth-First Search, Breadth-First Search
- Range Sum of BST Depth-First Search, Binary Search
- Increasing Order Search Tree Depth-First Search, Stack
- Leaf-Similar Trees Depth-First Search
- Search in a Binary Search Tree Binary Search
- Second Minimum Node In a Binary Tree Depth-First Search
- Two Sum IV - Input is a BST Depth-First Search, Hash Table, Two Pointers
- Merge Two Binary Trees Depth-First Search, Breadth-First Search
- Subtree of Another Tree Depth-First Search, String Matching
- Binary Tree Tilt Depth-First Search
- Diameter of Binary Tree Depth-First Search
- Minimum Absolute Difference in BST Depth-First Search, Breadth-First Search
- Find Mode in Binary Search Tree Depth-First Search
- Sum of Left Leaves Depth-First Search, Breadth-First Search
- Binary Tree Paths Depth-First Search, Backtracking, String
- Invert Binary Tree Depth-First Search, Breadth-First Search
- Path Sum Depth-First Search, Breadth-First Search
- Balanced Binary Tree Depth-First Search
- Minimum Depth of Binary Tree Depth-First Search, Breadth-First Search
- Maximum Depth of Binary Tree Depth-First Search, Breadth-First Search
- Symmetric Tree Depth-First Search, Breadth-First Search
- Same Tree Depth-First Search, Breadth-First Search
- Binary Tree Postorder Traversal Depth-First Search, Stack
- Binary Tree Preorder Traversal Depth-First Search, Stack
- Binary Tree Inorder Traversal Depth-First Search, Stack
Medium (92)
- Operations on Tree Array, Hash Table, Depth-First Search
- Throne Inheritance Hash Table, Depth-First Search, Design
- Convert Sorted List to Binary Search Tree Linked List, Divide and Conquer, Recursion
- Foldable Binary Tree Depth-First Search, Recursion
- K-th Largest Perfect Subtree Size in Binary Tree Depth-First Search, Sorting
- Duplicate Subtree in Binary Tree Hash Table, Depth-First Search
- Sum of Nodes on the Longest Path from Root to Leaf Depth-First Search
- Largest BST in a Binary Tree Depth-First Search, Dynamic Programming
- Median of BST Depth-First Search
- Predecessor and Successor in BST Binary Search
- Inorder Successor in BST Binary Search, Depth-First Search
- Floor in BST Binary Search
- Minimum Distance Between Two Given Nodes of a Binary Tree Depth-First Search
- Sum Tree Depth-First Search, Recursion
- Vertical Sum of Binary Tree Hash Table, Depth-First Search
- Diagonal Traversal of Binary Tree Depth-First Search, Queue
- Boundary Traversal of Binary Tree Depth-First Search
- Bottom View of Binary Tree Breadth-First Search, Hash Table
- Top View of Binary Tree Breadth-First Search, Hash Table
- Cousins in Binary Tree II Breadth-First Search, Hash Table
- Kth Largest Sum in a Binary Tree Breadth-First Search, Sorting, Heap (Priority Queue)
- Closest Nodes Queries in a Binary Search Tree Binary Search, Depth-First Search, Array
- Minimum Number of Operations to Sort a Binary Tree by Level Breadth-First Search, Sorting
- Reverse Odd Levels of Binary Tree Depth-First Search, Breadth-First Search
- Amount of Time for Binary Tree to Be Infected Breadth-First Search, Depth-First Search
- Count Nodes Equal to Average of Subtree Depth-First Search
- Create Binary Tree From Descriptions Hash Table, Array
- Step-By-Step Directions From a Binary Tree Node to Another Depth-First Search, String
- Even Odd Tree Breadth-First Search
- Number of Good Leaf Nodes Pairs Depth-First Search
- Pseudo-Palindromic Paths in a Binary Tree Depth-First Search, Bit Manipulation
- Count Good Nodes in Binary Tree Depth-First Search, Breadth-First Search
- Longest ZigZag Path in a Binary Tree Depth-First Search, Dynamic Programming
- Linked List in Binary Tree Depth-First Search
- Maximum Product of Splitted Binary Tree Depth-First Search
- Delete Leaves With a Given Value Depth-First Search
- Sum of Nodes with Even-Valued Grandparent Depth-First Search, Breadth-First Search
- All Elements in Two Binary Search Trees Depth-First Search, Sorting
- Deepest Leaves Sum Breadth-First Search, Depth-First Search
- Maximum Level Sum of a Binary Tree Breadth-First Search
- Binary Tree Coloring Game Depth-First Search
- Insufficient Nodes in Root to Leaf Paths Depth-First Search
- Maximum Difference Between Node and Ancestor Depth-First Search
- Construct Binary Search Tree from Preorder Traversal Array, Stack, Binary Search
- Maximum Binary Tree II Binary Search
- Smallest String Starting From Leaf String, Backtracking, Depth-First Search
- Distribute Coins in Binary Tree Depth-First Search
- Check Completeness of a Binary Tree Breadth-First Search
- Flip Equivalent Binary Trees Depth-First Search
- Smallest Subtree with all the Deepest Nodes Hash Table, Depth-First Search, Breadth-First Search
- All Nodes Distance K in Binary Tree Hash Table, Depth-First Search, Breadth-First Search
- Binary Tree Pruning Depth-First Search
- Insert into a Binary Search Tree Binary Search
- Longest Univalue Path Depth-First Search
- Trim a Binary Search Tree Depth-First Search, Recursion
- Maximum Width of Binary Tree Depth-First Search, Breadth-First Search
- Maximum Binary Tree Array, Divide and Conquer, Stack
- Add One Row to Tree Depth-First Search, Breadth-First Search
- Convert BST to Greater Tree Depth-First Search, Binary Search
- Find Largest Value in Each Tree Row Depth-First Search, Breadth-First Search
- Find Bottom Left Tree Value Depth-First Search, Breadth-First Search
- Most Frequent Subtree Sum Hash Table, Depth-First Search
- Delete Node in a BST Binary Search, Recursion
- Path Sum III Depth-First Search, Prefix Sum, Hash Table
- House Robber III Depth-First Search, Dynamic Programming
- Lowest Common Ancestor of a Binary Tree Depth-First Search
- Lowest Common Ancestor of a Binary Search Tree Binary Search, Depth-First Search
- Kth Smallest Element in a BST Depth-First Search
- Binary Tree Right Side View Breadth-First Search, Depth-First Search
- Sum Root to Leaf Numbers Depth-First Search
- Flatten Binary Tree to Linked List Depth-First Search, Stack
- Path Sum II Depth-First Search, Backtracking
- Binary Tree Level Order Traversal II Breadth-First Search
- Construct Binary Tree from Inorder and Postorder Traversal Array, Hash Table, Divide and Conquer
- Construct Binary Tree from Preorder and Inorder Traversal Array, Hash Table, Divide and Conquer
- Binary Tree Zigzag Level Order Traversal Breadth-First Search
- Binary Tree Level Order Traversal Breadth-First Search
- Recover Binary Search Tree Depth-First Search
- Validate Binary Search Tree Depth-First Search
- Construct String from Binary Tree Depth-First Search, String
- Minimum Increments to Equalize Leaf Paths Array, Dynamic Programming, Depth-First Search
- Maximize the Number of Target Nodes After Connecting Trees I Depth-First Search, Breadth-First Search
- Find Subtree Sizes After Changes Array, Hash Table, String
- Count the Number of Good Nodes Depth-First Search
- Validate Binary Tree Nodes Depth-First Search, Breadth-First Search, Union Find
- Maximum Score After Applying Operations on a Tree Dynamic Programming, Depth-First Search
- Count Nodes With the Highest Score Array, Depth-First Search, Binary Search
- Most Profitable Path in a Tree Array, Depth-First Search, Graph
- Number of Nodes in the Sub-Tree With the Same Label Hash Table, Graph, Depth-First Search
- Minimum Fuel Cost to Report to the Capital Graph, Depth-First Search, Breadth-First Search
- Reachable Nodes With Restrictions Array, Graph, Depth-First Search
- Time Needed to Inform All Employees Depth-First Search, Breadth-First Search
Hard (20)
- Maximum Path Sum Between Two Leaves Depth-First Search, Recursion
- Height of Binary Tree After Subtree Removal Queries Depth-First Search, Breadth-First Search, Array
- Maximum Sum BST in Binary Tree Depth-First Search, Dynamic Programming, Recursion
- Recover a Tree From Preorder Traversal Depth-First Search, String, Stack
- Vertical Order Traversal of a Binary Tree Depth-First Search, Breadth-First Search, Hash Table
- Binary Tree Cameras Depth-First Search, Dynamic Programming, Greedy
- Binary Tree Maximum Path Sum Depth-First Search, Dynamic Programming, Recursion
- Maximize the Number of Target Nodes After Connecting Trees II Depth-First Search, Breadth-First Search
- Time Taken to Mark All Nodes Depth-First Search, Graph, Dynamic Programming
- Maximum Number of K-Divisible Components Depth-First Search
- Count Valid Paths in a Tree Math, Dynamic Programming, Depth-First Search
- Minimum Edge Weight Equilibrium Queries in a Tree Array, Graph
- Minimize the Total Price of the Trips Array, Dynamic Programming, Depth-First Search
- Collect Coins in a Tree Array, Graph, Topological Sort
- Create Components With Same Value Array, Math, Depth-First Search
- Minimum Score After Removals on a Tree Array, Bit Manipulation, Depth-First Search
- Maximum Points After Collecting Coins From All Nodes Array, Dynamic Programming, Bit Manipulation
- Sum of Distances in Tree Depth-First Search, Graph, Dynamic Programming
- Longest Path With Different Adjacent Characters Array, String, Depth-First Search
- Number of Good Paths Array, Graph, Union Find
Companies that ask trees problems
- Amazon 147 problems on trees
- Google 85 problems on trees
- Microsoft 72 problems on trees
- Meta 39 problems on trees
- Bloomberg 15 problems on trees
- Samsung 8 problems on trees
- LinkedIn 5 problems on trees
- Flipkart 3 problems on trees
- Uber 3 problems on trees
- Adobe 2 problems on trees
- Paytm 2 problems on trees
- Salesforce 2 problems on trees
Next topic: Trie