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

Binary Tree Preorder Traversal

Real-world version: Survey Order Of A Ventilation Split
Tracked in this browser only
Read Binary Tree Preorder 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 mine's air supply runs from a single head junction. Every junction sends air on through at most two drifts, one off its left wall and one off its right wall, and each junction carries a signed airflow reading.

Because the harness takes plain JSON, the network arrives as the array junctions, written out depth by depth. junctions[0] is the reading at the head junction. The entries after it come in pairs, giving the left-wall drift and then the right-wall drift of each junction already written out, taken in the same order those junctions were written. A wall with no drift is written null, and a null never claims a pair of its own. Trailing null entries are left off the end, and an empty array means the network was never dug.

A surveyor walks the network like this: on arriving at a junction they write down its reading, then they walk everything hanging off its left wall, and only once that is finished do they walk everything hanging off its right wall.

Return the readings in the order the surveyor writes them down, or an empty list if the network was never dug.

Examples

Example 1

Input
junctions = [42, -8, 17, null, 5, 61]
Output
[42, -8, 5, 17, 61]

The head junction reads 42. Its left-wall drift leads to -8, which has no left drift and a right drift to 5. Once that side is finished the walk crosses to 17 and then to 61.

Example 2

Input
junctions = [90]
Output
[90]

The network is a single junction, so the surveyor writes one reading.

Example 3

Input
junctions = [-3, 26, null, null, 74, 12, -55]
Output
[-3, 26, 74, 12, -55]

The head junction reads -3 and its left wall leads to 26. That junction has nothing off its left wall, and its right wall leads to 74, whose two drifts read 12 and -55.

Constraints

  • 0 <= number of junctions <= 100
  • -100 <= airflow reading <= 100
  • 0 <= junctions.length <= 201
  • Every entry of junctions is either null or an integer reading
  • junctions[0] is a reading whenever junctions is non-empty

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 survey_order(junctions: list) -> list[int]:
Java
public List<Integer> surveyOrder(Integer[] junctions)

More on the same topics