Show problems as
Classic problem #94EasyStackTreeDepth-First SearchBinary Tree

Binary Tree Inorder Traversal

Real-world version: Manifold Valve Readout
Tracked in this browser only
Read Binary Tree Inorder Traversal on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTraversal · Binary Trees & BST, animated step by step

A test rig pushes fluid through a branching manifold. Every valve carries a stamped tag and has two outlets, a near tap and a far tap, each of which either feeds another valve or is capped.

The manifold reaches you flattened into the list manifold, written one rank at a time from the top valve downward and left to right inside a rank. Each valve that appears claims the next two entries of the list as its near tap and its far tap, in that order, where null marks a capped tap. A capped tap claims no entries of its own. Trailing entries that would record nothing but caps are left off, and an empty list means the rig holds no valves.

A technician always reads the rig in the same order: everything fed by a valve's near tap, then that valve's own tag, then everything fed by its far tap. Return the tags in the order the technician reads them. Tags may repeat, and a rig with no valves reads as an empty list.

Examples

Example 1

Input
manifold = [2, 9, 1, -7, 4, null, -3]
Output
[-7, 9, 4, 2, 1, -3]

Valve 9 feeds -7 on its near tap and 4 on its far tap, so that whole branch reads -7, 9, 4 before the top valve 2. Valve 1 has a capped near tap, so it is read before -3.

Example 2

Input
manifold = [3, 2, null, 1]
Output
[1, 2, 3]

Each valve only feeds a near tap, so the deepest valve is read first and the top valve last.

Example 3

Input
manifold = [5, 5, 5]
Output
[5, 5, 5]

Repeated tags are reported once per valve, so the readout keeps all three.

Constraints

  • The rig holds between 0 and 100 valves
  • -100 <= tag of a valve <= 100
  • manifold entries are integers or null, and the list encodes one real manifold as described

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def valve_readout(manifold: list) -> list[int]:
Java
public List<Integer> valveReadout(Integer[] manifold)

More on the same topics