FastPrepRebuild Binary Tree from Level Order

Rebuild Binary Tree from Level Order

Bloomberg LP logoBloomberg LP● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

levelOrder is a compact breadth-first serialization of a binary tree. The first value is the root. For each non-null node removed from a queue, the next value (if present) is its left child and the following value (if present) is its right child. nullMarker means that child is absent and is never a real node value. Trailing absent children may be omitted.

Rebuild the tree and return its preorder serialization, writing nullMarker for every absent left or right child.

Function

levelOrderToPreorder(levelOrder: int[], nullMarker: int) → int[]

Examples

Example 1

levelOrder = [1,2,3,-1,4,-1,5]nullMarker = -1return = [1,2,-1,4,-1,-1,3,-1,5,-1,-1]

Node 1 has children 2 and 3; node 2 has only right child 4; node 3 has only right child 5. Preorder records each missing child as -1.

Constraints

  • 1 <= levelOrder.length <= 100000.
  • The encoding is valid and completely consumed by the reconstruction rule.
  • Every real node value differs from nullMarker.
  • If the root equals nullMarker, it is the only input entry.

More Bloomberg LP problems

See Bloomberg LP hiring insights
public int[] levelOrderToPreorder(int[] levelOrder, int nullMarker) {
  // Write your code here.
}
levelOrder[1,2,3,-1,4,-1,5]
nullMarker-1
expected[1,2,-1,4,-1,-1,3,-1,5,-1,-1]
Checking account…