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 1:
Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Example 2:
Input: preorder = [1,3] Output: [1,null,3]
Constraints:
1 <= preorder.length <= 1001 <= preorder[i] <= 1000preorder are unique.In this approach, you will construct the binary search tree (BST) by recursively inserting nodes. The property of the BST is used where, for each node, nodes in the left subtree are less, and nodes in the right subtree are greater.
Start with the first element from the preorder sequence, which will be the root. Recursively insert subsequent elements using the BST insertion logic, and this will ensure that the tree constructed respects both the structure of a BST and adheres to the given preorder traversal.
This C solution recursively inserts each element of the preorder array into the BST using standard recursive insertion. Starting with the first element as the root, it iteratively adds each subsequent element by comparing values and guiding the insertion either to the left or the right subtree appropriately.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) in the worst case due to skewed trees where each insertion is O(n).
Space Complexity: O(n) due to the recursion stack and additional space for the BST nodes.
This approach uses a stack to iteratively construct the BST from the preorder traversal, which helps in achieving better average performance. Begin with the root node from the first preorder element, and iterate over the rest of the array with a technique to adjust parents as potential ancestors using a stack. Primary benefit is an average O(n log n) time complexity due to more constant-time parent-backtracking via stack use.
This C implementation uses an auxiliary stack structure to iteratively build the BST. By iterating over the preorder list, it appends each node either as a left child (when smaller) or as a right child using the stack to backtrack dynamically to suitable parent nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), processing each node in a single pass with constant-time stack operations.
Space Complexity: O(n) due to the usage of an explicit stack for nodes.
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Insertion | Time Complexity: O(n^2) in the worst case due to skewed trees where each insertion is O(n). |
| Approach 2: Stack-based Iterative Construction | Time Complexity: O(n), processing each node in a single pass with constant-time stack operations. |
Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python • NeetCode • 307,238 views views
Watch 9 more video solutions →Practice Construct Binary Search Tree from Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor