Exchange Relay Inspection

Minimum walk length from a binary tree's root visiting all nodes valued 1

MediumTreesTree Dynamic ProgrammingDepth-First Search

A stock exchange connects its message relays in a binary tree. Each relay has a status value:

  • 1 means the relay requires an inspection.
  • 0 means no inspection is required there.

An inspector starts at the root. One move takes the inspector along one tree edge, either from a parent to a child or from a child to its parent. A relay is inspected as soon as the inspector visits it, so the root is inspected immediately if its value is 1.

The inspector must visit every relay whose value is 1. Relays and edges may be revisited, and the inspector may finish at any relay without returning to the root.

Return the minimum number of moves needed to complete all required inspections. Return 0 if the tree is empty or no relay requires inspection.

Examples

Example 1

Input: root = [0,1,1]
Output: 3

Both children require inspection. The inspector can visit one child, return to the root, and finish at the other child.

Example 2

Input: root = [0,0,1,1,null,null,1]
Output: 6

Required relays occur on both sides of the root. The inspector must explore both branches, but can avoid retracing the final branch back to the root.

Example 3

Input: root = [0,0,0]
Output: 0

No relay requires inspection, so the inspector does not need to move.

Constraints

  • The tree contains between 0 and 12,000 nodes.
  • Every node value is either 0 or 1.
  • The input is a valid binary tree.

Use an iterative traversal to support trees whose height is as large as the node count. The intended solution takes O(n) time and O(n) auxiliary space.

Hints

Show hint 1

Which edges must be used at least once to reach every required relay from the root?

Show hint 2

Every necessary edge normally needs a trip in both directions. Which edges can avoid the return trip when the inspector may finish anywhere?

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would the answer change if the inspector had to return to the root?
  • How would you solve the problem if the inspector could choose both the starting and finishing relays?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem