Tree Traversal and Efficient Target Search | Dataford Interview Questions

A Google DeepMind evaluation tree stores integer values in a binary tree. Given the tree root and a target value, return the minimum number of edges from the root to any node containing the target. Return -1 if the target does not occur.

Use breadth-first search so nodes are examined level by level. This guarantees that the first matching node found is at the minimum depth, even when duplicate values occur.

Formal Specification

The function receives root, either None or a nested dictionary with the form {"val": integer, "left": node_or_None, "right": node_or_None}, and an integer target. Return an integer representing the minimum root-to-target edge count. The root is at depth 0.

Constraints

0 <= number of nodes <= 10^5
Node values and target are integers in [-10^9, 10^9]
The tree may be highly unbalanced
Duplicate node values are allowed

Function Signature

def minimum_target_depth(root, target):

Your question is Tree Traversal and Efficient Target Search. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem