Construct BST From Preorder Traversal

Construct BST From it's preorder traversal

Analysis

The binary search tree's preorder traversal can be build using stack, intuitively we can aslo use stack to rebuild the tree from preorder traversal.

For one dimension problem, we can always start of thinking how to handle the two cases: consecutive increasing order and consecutive decreasing order and the state flip.

For example:

consecutive increasing order:

[1, 2, 3, 4, 5, 6]

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

consecutive decreasing order:

[6, 5, 4, 3, 2, 1]

          6
         /
        5
       /
      4
     /
    3
   /
  2
 /
1

consecutive increasing flip to consecutive deceasing:

[1, 2, 5, 4, 3]

1
 \
  2
   \
    5
   /
  4
 /
3

consecutive decreasing flip to consecutive increaseing:

[6, 4, 1, 2, 3, 5]

              6
             /
            4
           / \
          1   5
           \
            2
             \
              3

One of the important feature of BST's preorder traversal is

If there is a consecutive decreasing order, node A whose value is number i is always the left node of node B whose value is number i-1.

Solution

class Solution(object):
    def bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        root = TreeNode(preorder[0])
        stack = [root]
        for v in preorder[1:]:
            node = TreeNode(v)
            if v < stack[-1].val:
                stack[-1].left = node
                stack.append(node)
            else:
                left_node = None
                while stack and stack[-1].val < v:
                    left_node = stack.pop()
                left_node.right = node
                stack.append(node)
        return root