# 1008. Construct Binary Search Tree from Preorder Traversal

Contents

Problem solution 1008 “Construct Binary Search Tree from Preorder Traversal” from LeetCode.

# Problem

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 2 `````` ``````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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func bstFromPreorder(preorder []int) *TreeNode { if len(preorder) == 0 { return nil } root := TreeNode{ Val: preorder[0], } for idx:=1;idx
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func bstFromPreorder(preorder []int) *TreeNode { cur := 0 return helper(preorder, 0, 1<<31 - 1, &cur) } func helper(preorder []int, prev int, max int, cur *int) *TreeNode{ if len(preorder) == 0 { return nil } if *cur == len(preorder) { return nil } if preorder[*cur]> max { return nil } root := &TreeNode { Val: preorder[*cur], } *cur++ root.Left = helper(preorder, root.Val, root.Val, cur) root.Right = helper(preorder, root.Val, max, cur) return root } ``````