Construct Binary Search Tree from Preorder Traversal

Introduction

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Constraints:

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
The values of preorder are distinct.

Solution

This is classical task for deserialization. If we know that right child always creater than root, sometimes it is faster to find this node and deserialize tree.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
    n := len(preorder)
    if n == 0 {
        return nil
    }
    node := &TreeNode { Val: preorder[0] }
    for i := 1; i < n; i++ {
        if preorder[i] > preorder[0] {
            node.Left = bstFromPreorder(preorder[1:i])
            node.Right = bstFromPreorder(preorder[i:])
            return node
        }
    }
    node.Left = bstFromPreorder(preorder[1:])
    return node
}

Performance

Hard to make better:

Runtime: 0 ms
Memory Usage: 3.2 MB