Search Tree From a Visit Log

Medium

A walk over a binary search tree wrote node values into the log visits in this order: the current node first, then its whole left subtree, then its whole right subtree (a preorder walk). In a search tree, every value in a node's left subtree is strictly smaller than the node's value and every value in its right subtree is strictly larger. All values are distinct. Rebuild the tree from the log and return its root. The log is guaranteed to come from some search tree.

Example 1

visits=[20, 11, 4, 15, 30, 25] → [20, 11, 30, 4, 15, 25]

The root is 20. The smaller values 11, 4, 15 go left: 11 with children 4 and 15. The larger 30, 25 go right: 30 with 25 as its left child.

Example 2

visits=[9, 6, 3] → [9, 6, None, 3]

Each value is smaller than the last, so the tree is a chain going left.

Example 3

visits=[500] → [500]

Constraints

1 ≤ len(visits) ≤ 100
1 ≤ visits[i] ≤ 1000
All values are distinct
visits is the preorder walk of some search tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Tree Binary Search Tree Array Binary Tree Monotonic Stack

Similar problems

Preorder of a Search Tree Medium Peak-Split Tree Medium Pair Across Two Search Trees Medium Search Tree Height From Insertion Order Medium Floor and Ceiling in a Search Tree Medium

Input

visits=[20, 11, 4, 15, 30, 25]

Expected

[20, 11, 30, 4, 15, 25]

Run checks the first 3 tests in your browser. Submit checks all 67 tests on the server, hidden ones included.