How deep does this tree go?

easyData Structures+150 XPPractice

Nested comment threads, category menus and file explorers all arrive as trees, and the first question is usually how deep they go: how far to indent, when to collapse, whether to warn that a reply is nested too far.

Implement maxDepth(node). A node is a plain object shaped { id, children } where children is an array of nodes; the children property may be missing entirely, which means the node has no children. Return the number of levels in the tree: 0 for null, 1 for a node with no children, and one more than the deepest child otherwise.

Arguments

node{ id: unknown; children?: Node[] } | null: The root of the tree, or null for no tree at all.

Returns

number — The number of levels in the tree — 0 for null, 1 for a leaf, one more than the deepest child otherwise.

Examples

maxDepth(null);
// 0

maxDepth({ id: "a" });
// 1 — a leaf has depth 1

maxDepth({
  id: "r",
  children: [
    { id: "a" },
    { id: "b", children: [{ id: "c" }] },
  ],
});
// 3 — the deepest branch wins

What it has to do

Return 0 when the node is null.
Return 1 for a leaf node, whether children is missing or an empty array.
Follow the deepest branch, not the first one.
Handle trees of any depth.

Notes

Runs in O(n) time — every node is visited exactly once — and O(h) call-stack space for a tree of height h.
Deeply nested threads can blow the stack with recursion. If you ever hit that, convert to an iterative traversal with an explicit stack of { node, depth } pairs.

Stuck? The javascript course covers everything this challenge needs.

Try it yourself· Edit the code, then press Run

Loading playground...

5 tests · +150 XP

Discussion

No comments yet. Be the first to say something.

All challenges101 / 150