[Google] Construct BST from given preorder traversal

Problem: Construct BST from given preorder traversal.

Approach: Straight forward to understand. Please look at the implementation for more understanding.

Implementation in C#:

    public TreeNode BstFromPreorder(int[] preorder) 

    {

        int index = 0;

        return this.BstFromPreorder(preorder, ref index, preorder[0], int.MinValue, int.MaxValue);

    }

    

    private TreeNode BstFromPreorder(int[] preorder, ref int index, int num, int min, int max)

    {

        if (index >= preorder.Length)

        {

            return null;

        }

        TreeNode node = null;

        if (num > min && num < max)

        {

            node = new TreeNode(num);

            ++index;

            if (index < preorder.Length)

            {

                node.left = BstFromPreorder(preorder, ref index, preorder[index], min, num);

            }

            

            if (index < preorder.Length)

            {

                node.right = BstFromPreorder(preorder, ref index, preorder[index], num, max);

            }

        }

        

        return node;

    }

Complexity: O(n)