How should I practice Next Leaf in an Ordered Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple phone screen problems in FastPrep.

Is Next Leaf in an Ordered Tree associated with Apple?

FastPrep tags this as a Apple phone screen coding practice problem when the problem catalog has that company and stage context.

Next Leaf in an Ordered Tree

Apple● MediumNEW GRADPHONE SCREEN

Learn

Problem statement

An ordered rooted tree has nodes numbered from 0 to children.length - 1. Node 0 is the root, and children[u] lists node u's children in left-to-right order. A node with an empty child list is a leaf.

Return the leaf immediately after leaf in a depth-first traversal that visits children in their listed order. Return -1 when the supplied leaf is last.

For this exercise, the input is one valid connected tree, and leaf names an existing leaf. The child order defines the meaning of next.

Function

nextLeaf(children: int[][], leaf: int) → int

Examples

Example 1

children = [[1,2],[3,4],[],[],[]]leaf = 4return = 2

The leaf order is [3,4,2], so leaf 2 follows leaf 4.

Example 2

children = [[1,2],[3,4],[],[],[]]leaf = 2return = -1

Leaf 2 is the final leaf.

Example 3

children = [[]]leaf = 0return = -1

The root is the only leaf.

Constraints

1 <= children.length <= 10^5.
Every child ID is a valid node ID.
Each non-root node has one parent, and the tree has no cycles.
leaf names a node whose child list is empty.