In this problem we’re given an input array of integers that represent the pre-order traversal of BST. Our solution will use this input to reconstruct the BST in the same pre-order traversal.
Example:
Approach 2:
Because in this problem our binary tree is binary search tree, we can use the pre-order traversal from the input array to output a unique BST. However, where order doesn’t matter we can have many different versions of the same pre-order traversal.
In this solution we’re iterating over the input array first identifying the left and right subtree index. To do this we find the first value less than then current node and the first value greater than the current node. This allows us to recursively iterate through the BST and add the nodes in the right order. We know that any value greater than the root node will be the right subtree, therefore as we move down the left subtree we are simply focusing on the left subtree and its sub trees. Moving the boundaries as we go.
This is not the most optimal solution since along from recursively iterating through the BST, for each node iteration we’re iterating over the input array to check the current boundary and determine its left and right child.
In our solution one important step is to keep track of our root index. The way we can do this and create a ‘global’ integer is to create a class called TreeInfo and add a mutable data point called rootIdx which would be mutable throughout the whole program. Unlike, a regular integer which when changed in one place it will not change everywhere.
Implementation
Complexity Analysis
Time Complexity: O(N2) — Iterating over the input array for each recursive call
Space Complexity: O(N) — The call stack for the recursive calls will create n space.
Approach 2:
In this solution we’re iterating over the input array once and the way we can keep track of the left and right child nodes is by creating a rootIdx and a range for each node. This allows us to increase the rootIdx which is a number in the input array, we check if its within the range for a left child if its then we add it then we increase the index. then we check if its in the range for a right child if not then don’t increase the index and simply move back up tree.
Implementation
Complexity Analysis
Time Complexity: O(N) — we have n recursive calls, therefore, n time.
Space Complexity: O(h) — the call stack is equal to the height of the tree.