Go solution to Leetcode 1008 Construct binary search tree from a preorder traversal

In this Leetcode problem, we are given a preorder traversal and should return the binary search tree matching with this preorder traversal.

Problem statement

I love tree problem, in particular the ones that are enunciated so simply.

I didn’t implement the most basic approach that uses divide and conquer. The approach would be the following:

• If the array is empty return nil
• Take the first element of the array A[0] = x and use it as a pivot
• Find the first index p such that A[p] > x, this takes O(ln(N)) which is why I didn’t do it in the end.
• Construct BST from preorder of A[0..p] (p excluded), call it L
• Construct BST from preorder of A[p..len(A)] (len(A) excluded), call it R
• The solution is &TreeNode(x, L, R)

Because I didn’t want to use the “expensive” binary search each step of the way. I chose a more iterative building approach (even if it is implemented recursively). It requires going through the array (and the tree) only once.

In the concept, it the the similar, but we keep track of the current position start in the array as we go through it, as well as the ancestor for which the value…