[Leetcode] #1008 Construct Binary Search Tree from Preorder Traversal(C++/Tree/Medium)

Hello! Today, we’ll look at a tree question on Leetcode.

Our goal is to find the proper BST from the given preorder traversal. Before diving into the solution, there are two intuitions we should catch.

1. Given the root, all nodes of the left-subtree have smaller values than the root and all nodes of the right-subtree have greater values than the root.
2. Preorder: Using the property of preorder-traversal = (print)(Left-Subtree)(Right-Subtree), the first node of each divided group is the “root node”. As you can see below, 8 is the root of the original tree, and 5, 10 are roots of the left and right sub-trees.

Let TreeNode* function(i,j) be a recursive function that returns the root of the tree represented by preorder_array[i,j]. Also, let temp be an index of the first element whose value is greater than the root->val.

Implementation

Time Complexity: O(n), where n is the number of nodes in the tree