How should I practice Binary Tree Nodes at Distance K?

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

Is Binary Tree Nodes at Distance K associated with Apple?

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

Problem · Tree

Binary Tree Nodes at Distance K

Learn this problem

● Medium

AppleFULLTIMEONSITE INTERVIEW

Problem statement

You are given a binary tree in nodes. Every row has the form [id, value, leftId, rightId], where a child ID of -1 means null. The first row is the root. Node IDs are unique, but node values do not have to be.

Given targetId and a nonnegative distance k, return the IDs of all nodes exactly k edges from the target. Tree edges can be traversed in either direction, so a result can lie below the target, above it, or in another branch. Return IDs in ascending order. If k exceeds every reachable distance, return an empty array.

Function

nodesAtDistanceK(nodes: int[][], targetId: int, k: int) → int[]

Examples

Example 1

nodes = [[1,3,2,3],[2,5,4,5],[3,5,-1,6],[4,6,-1,-1],[5,2,7,8],[6,1,-1,-1],[7,7,-1,-1],[8,4,-1,-1]]targetId = 2k = 2return = [3,7,8]

From node ID 2, node IDs 3, 7, and 8 are exactly two edges away.

Example 2

nodes = [[10,9,20,-1],[20,9,-1,-1]]targetId = 20k = 0return = [20]

Distance zero contains the target itself. Equal values do not merge the two node identities.

Example 3

nodes = [[4,1,-1,-1]]targetId = 4k = 3return = []

No node is three edges from the only node in the tree.

Constraints

1 <= nodes.length <= 100000.
Every row contains exactly [id, value, leftId, rightId].
Node IDs are distinct nonnegative 32-bit integers; child IDs are -1 or reference another row.
Values are signed 32-bit integers and may repeat.
The rows describe one valid connected binary tree, and the first row is its root.
targetId is present in the tree.
0 <= k <= 100000.
Return matching node IDs in ascending order.