The blog for Design Patterns, Linux, HA and Myself!

Construct Binary Search Tree From Preorder Traversal Solution

Leetcode Solution: Understand Leetcode problem Construct Binary Search Tree From Preorder Traversal(1008) Solution

In this article we’ll be solving the problem: Construct Binary Search Tree from Preorder Traversal. Just like the problem, Maximum Binary Tree and Convert Sorted Array to BST, this problem falls into the category of those problems in which the tree is created from an input array.

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]
            / \
           5   10
          / \    \
         1   7    12

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


The array will contain the pre order tree traversal for the binary search tree. Since it’s a pre order tree traversal output it means that the first element from the array will be the root element and since it’s a binary search tree the elements in the left subtree will be those elements that are lower than the first element(root), and the elements greater than the first element will form the right subtree.

We’ll be using the following array as the example input to understand the solution:

input := []int{8, 5, 1, 7, 10, 12}

To solve this problem, we’ll

  1. pick the first element and make it the root (8)
  2. find the elements for the left subtree (5, 1, 7)
  3. find the elements for the right subtree (10, 12)
  4. perform the steps 1, 2, 3 on the array found in step 2
  5. perform the steps 1, 2, 3 on the array found in step 3

Here’s the first split that we’ve done after finding 8 as the root element:

1st call

We found two sub arrays that’ll be two subtrees. In the left subtree, we find 5 as the root of the left subtree and then we divide the array into two parts, [1] and [7] as 5 was the first element in that sub array.

2nd call

We’ve completed the left sub tree. Now, we’re moving to the right subtree, [10, 12]:

3rd call

Finally, here’s the tree that we’ve created through from the previous steps:

Full tree after the creation

Here is the program for that:

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode

func bstFromPreorder(preorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    return construct(preorder, 0, len(preorder) - 1)

func construct(preorder []int, start, end int) *TreeNode {
    if start > len(preorder) || start < 0 || end > len(preorder)  || start > end {
        return nil
    val := preorder[start]
    partition := findPartition(preorder, val, start, end)
    node := &TreeNode {
        Val: val,
    if partition == -1 {
        node.Left = construct(preorder, start + 1, end)    
    } else {
        node.Left = construct(preorder, start + 1, partition - 1)    
    node.Right =  construct(preorder, partition, end)
    return node

func findPartition(preorder []int, val, start, end int) int {
    fmt.Println(val, start, end)
    if start > len(preorder) || start < 0 || end > len(preorder)  || start > end {
        return -1
    for i := start; i <= end; i++ {
        if preorder[i] > val {
            return i
    return -1

The logic remains same to what we’ve discussed earlier. The function bstFromPreorder calls the function construct by passing the entire array. Then construct calls itself recursively after finding the partition index and dividing the array into sub array. Here, we’re not actually dividing the array as we’re finding the start and the end indices on which function has to operate as the sub problem. The function findPartition is a very simple function with the responsibility of finding the partition index from the array between the start and the end indices.

This program can be found on GitHub as well.

Loading Comments... Disqus Loader
comments powered by Disqus