Construct Binary Search Tree from Preorder Traversal

Problem Id: 1008 Difficulty: Medium Tag: Tree


Intuition

This could be solved recursively. The root princeple is that, for any preorder [a0, a1, a2, ... an], find the smallest j where aj > a0, then a1, a2, ..., a(j-1) is on its left sub-tree and others are on its right sub-tree.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        return self._helper(0, len(preorder), preorder)

    def _helper(self, lo, hi, preorder):
        if lo >= hi:
            return None
        node = TreeNode(preorder[lo])
        mid = lo + 1
        while mid < hi and preorder[mid] < preorder[lo]:
            mid += 1
        node.left = self._helper(lo + 1, mid, preorder)
        node.right = self._helper(mid, hi, preorder)
        return node