Show problems as
Classic problem #105MediumArrayHash TableDivide and ConquerTreeBinary Tree

Construct Binary Tree from Preorder and Inorder Traversal

Real-world version: Cave Survey Rebuild
Tracked in this browser only
Read Construct Binary Tree from Preorder and Inorder Traversal on LeetCode(opens in a new tab)

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

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

A caving club has surveyed a dry cave system. Each chamber carries its own depth marker, no two markers alike, and from any chamber at most two passages lead onward: a near one and a far one. A single chamber serves as the entrance.

Two teams walked the system, and both always took a chamber's near passage before its far passage.

  • The descent team wrote down a chamber's marker the moment they stepped into it, then covered everything behind its near passage, then everything behind its far passage. Their log arrives as entry_order.
  • The wall team covered everything behind the near passage first, wrote down the marker of the chamber they were standing in next, and covered the far passage last. Their log arrives as wall_order.

Because the markers are all different, exactly one layout produces both logs. Rebuild it and hand it back level by level, beginning with the entrance. Every chamber that exists puts two slots on the level below it, near slot before far slot, holding either the marker of the chamber found there or null when that passage does not exist. Any null slots trailing after the final marker are left off the answer.

Examples

Example 1

Input
entry_order = [10, 4, -8, 6, 17, 25, 20], wall_order = [-8, 4, 6, 10, 17, 20, 25]
Output
[10, 4, 17, -8, 6, null, 25, null, null, null, null, 20]

Marker 10 is the entrance, and the wall log puts -8, 4 and 6 on its near side, so 4 heads that branch with -8 and 6 hanging off it. On the far side 17 has no near passage, and its far passage leads to 25, whose own near passage reaches 20.

Example 2

Input
entry_order = [1, -9, 4, 2], wall_order = [-9, 2, 4, 1]
Output
[1, -9, null, null, 4, 2]

Every chamber sits on the near side of the entrance, so 1 has no far passage at all, and the branch below alternates sides on the way down.

Example 3

Input
entry_order = [42], wall_order = [42]
Output
[42]

A system of one chamber has no passages, so the answer holds just the entrance marker with no trailing null slots.

Constraints

  • 1 <= entry_order.length <= 3000
  • wall_order.length == entry_order.length
  • -3000 <= entry_order[i], wall_order[i] <= 3000
  • All markers in entry_order are distinct, and wall_order is a rearrangement of entry_order
  • The two logs are guaranteed to come from one real cave system, walked 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 rebuild_cave(entry_order: list[int], wall_order: list[int]) -> list:
Java
public Integer[] rebuildCave(int[] entryOrder, int[] wallOrder)

More on the same topics