Find the path to a node in a tree

mediumData Structures+250 XPPractice

Search a nested file tree or a category menu, land on a match, and now the UI has to expand every ancestor to reveal it and draw a breadcrumb. That means knowing the whole path, not just the node.

Implement findPath(root, targetId). root is a node shaped { id, children } where children is an array of nodes and may be missing. Return an array of id values leading from the root to the node whose id equals targetId, inclusive of both ends. When the root itself is the target, return an array holding just its id. When no node matches, return an empty array. When several nodes could match, return the path to the first one found by a depth-first pre-order walk with siblings in array order.

Arguments

root{ id: unknown; children?: Node[] } | null: The root of the tree to search.
targetIdunknown: The id of the node whose path is wanted.

Returns

unknown[] — The ids from the root to the matching node, inclusive, or [] when nothing matches.

Examples

const tree = { id: "root", children: [
  { id: "a", children: [{ id: "a1" }, { id: "a2", children: [{ id: "a2x" }] }] },
  { id: "b" },
]};
findPath(tree, "a2x");
// ["root", "a", "a2", "a2x"]

findPath({ id: "root" }, "root");
// ["root"] — the root itself is a valid match

findPath({ id: "root", children: [{ id: "a" }] }, "missing");
// [] — no match

What it has to do

Return the ids from the root down to the target, inclusive.
Return an array with a single id when the root is the target.
Return an empty array when nothing matches.
Search branches in array order and stop at the first match.
Treat a missing children property as no children.

Notes

Worst case O(n) time — the target could sit in the last branch — with O(h) stack space.
The clean trick is letting the recursion return the empty array for 'miss' and a non-empty path for 'hit', so the caller just prepends its own id to any non-empty result.

Stuck? The javascript course covers everything this challenge needs.

Try it yourself· Edit the code, then press Run

Loading playground...

5 tests · +250 XP

Discussion

No comments yet. Be the first to say something.

All challenges114 / 150