Tuesday, February 17, 2015

[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)

No comments:

Post a Comment