Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 20m 23s17 days 22 hours 20 minutes 23 seconds.

Algorithms - Trees and Range Queries · 4:15

Tree Basics

A tree is a connected graph without cycles: n - 1 edges and exactly one path between any two vertices. We pick up a 10-vertex tree by vertex 1 to root it, fill parent and depth with a dfs(v, p) that skips its parent instead of keeping a visited array, and let subtree sizes bubble up from the leaves. A path of 200,000 vertices crashes the recursive version on this Mac's 8 MB stack, so we redo it with a BFS order walked backwards, which handles a million vertices in milliseconds.

You will learn

State the equivalent definitions of a tree and use the unique-path property
Root a tree and compute parent, depth and subtree size in one O(n) DFS that skips the parent instead of keeping visited[]
Explain why recursion fails on deep (path-shaped) trees and compute the same arrays with a BFS order walked backwards
Handle input given as a parent array or an edge list, 1-indexed, with a consistent sentinel for the root's parent

Chapters

PreviousPrim's Minimum Spanning Tree NextDiameter and Farthest Distances