FastPrep
Problem · Tree

Reconstruct a BST from Preorder

Learn this problem
● MediumLyft logoLyftFULLTIMEPHONE SCREEN

Problem statement

You are given an integer array preorder, the preorder traversal of a valid binary search tree with unique values. Reconstruct the tree and return its canonical preorder serialization with null markers.

Serialize a node as its decimal value, followed recursively by its left subtree and right subtree. Serialize a missing child as #, and join all tokens with commas and no spaces. This encoding preserves the complete reconstructed shape.

Function

reconstructBST(preorder: int[]) → String

Examples

Example 1

preorder = [8,5,1,7,10,12]return = "8,5,1,#,#,7,#,#,10,#,12,#,#"

The root is 8. Values 5, 1, 7 form its left subtree, while 10, 12 form its right subtree. Null markers preserve every missing child.

Example 2

preorder = [1]return = "1,#,#"

The single node has two missing children.

Example 3

preorder = [5,4,3,2,1]return = "5,4,3,2,1,#,#,#,#,#,#"

Every later value belongs to the left subtree, producing a left-skewed BST.

Constraints

  • 1 <= preorder.length <= 1000.
  • -10^9 <= preorder[i] <= 10^9.
  • All values are unique.
  • preorder is guaranteed to be the preorder traversal of a valid BST.

More Lyft problems

drafts saved locally
public String reconstructBST(int[] preorder) {
    // Write your code here.
}
preorder[8,5,1,7,10,12]
expected"8,5,1,#,#,7,#,#,10,#,12,#,#"
checking account