This condition if evaluated to true indicates that each element is now included in BST.ĥ. If currIndex >= preorder.length return null. Call deserializeArrayOptimized(preorderArray = preorder, currIndex = currIndex, min = min, max = max)ģ. Initialize currIndex to 0, min to Integer.MIN_VALUE and max to INTEGER.MAX_VALUE.Ģ. To construct a binary search tree out of given pre-order traversal array, we check if the element's value satisfies constraints for BST and if it does then we construct a node out of it and advance the index in pre-order traversal array.ġ. This algorithm makes use of binary search tree(BST) property that - values of all the nodes in the left sub-tree of a given node are less than given node's value and values of all the nodes in the right sub-tree of a given node are greater than given node's value. Now let's look at the algorithm, which runs in O(n) time. For example, above algorithm takes O(n^2) time to construct BST for pre-order traversal array. Worst case comes into play when the BST to be constructed is skewed. Worst case time complexity for this method is O(n^2). After step#3, left and right sub-trees for root are constructed and we return root to the calling function. Second recursive call - root.right = deserializeArray(preorderArray = preorder, lowIndex = divIndex, highIndex = highIndex).Ĥ. Using this divIndex, we make recursive calls to create left and right sub-trees out of lower half and greater half of array respectively. įirst recursive call - root.left = deserializeArray(preorderArray = preorder, lowIndex = lowIndex + 1, highIndex = divIndex-1). Also all the elements in preorder array between indices (lowIndex + 1) and (divIndex - 1) (including both extremes) are going to be smaller than root node's value(lower half).ģc. All elements in the preorder array between the divIndex (including divIndex) and highIndex are going to be greater than root node's value (greater half). Find the index of the first element in preorder array which is greater than root value. If (low > high) return null This is the base case for this algorithm.ģa. Call deserializeArray(preorderArray = preorder, lowIndex = 0, highIndex = preorder.length-1).Ģ. Putting these ideas in a formal algorithm -ġ. The base case for this recursion would be that if the array size is 0, then we return an empty tree. In short, this problem can be solved using recursion. And to create right sub-tree of root 5, we need to solve sub-problem: given pre-order traversal array construct BST.Īs you can see, given problem is now reduced to two sub-problems with same definition but with smaller array sizes. Hence to create left sub-tree of root 5, we need to solve sub-problem: given pre-order traversal array, construct BST. Also, all the elements which are less than 5 would be placed in the left sub-tree(2,1,3,4) and elements greater than 5 would be placed in the right sub-tree(7,6,8).Notice that sub-arrays and are also pre-order traversals of left and right sub-trees respectively. Because this is a pre-order traversal array, first element of this array that is 5 must be the root of the BST. We will try to understand this algorithm using pre-order traversal array. Here the basic idea that we are going to use is that pre-order traversal visits a given tree in N-L-R fashion(N:Node, L:Left sub-tree, R:Right sub-tree) and the tree that we are going to construct is a BST. First one, a more intuitive but takes more time than the second one. To solve this problem, we will go through two algorithms here. The main problem we are going to solve is how to construct this BST given pre-order traversal array. For serialization, we can simply do a pre-order traversal of a given BST and store it in an array.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |