1008. Construct Binary Search Tree from Preorder Traversal

Problem Statement

link: LeetCode.cn LeetCode Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Example:

Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]

Input: preorder = [1,3] Output: [1,null,3]

Solution Approach

The solution constructs a binary search tree from the preorder traversal array by recursively partitioning the array into left and right subtrees based on each node’s value, utilizing depth-first search. The time complexity of the solution is O(n), where n is the number of nodes in the tree.

Algorithm

1. Define Recursive Function: Define a recursive function to construct the binary search tree from the preorder traversal array.
2. Partitioning: Partition the preorder array based on the values of the nodes, identifying the left and right subtrees for each node.
3. Build Tree Nodes: Recursively create tree nodes for each element in the preorder array, ensuring the left subtree contains values less than the current node and the right subtree contains values greater than the current node.

Implement

    Definition for a binary tree node. class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        def dfs(l, r):
            if l == r:
                return TreeNode(preorder[l])
            if l > r:
                return None
            val = preorder[l]
            node = TreeNode(val)
            pos = l + 1
            while pos < self.n and preorder[pos] < val:
                pos += 1
            node.left = dfs(l + 1, pos - 1)
            node.right = dfs(pos, r)
            return node
        
        self.n = len(preorder)
        return dfs(0, self.n - 1)

    
    

Twitter  facebook  Email