![]() 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. ![]() There are various ways of parsing the tree.For serialization, we can simply do a pre-order traversal of a given BST and store it in an array. 1 > Serializing the Binary Tree to string How to traves the treeĪ binary tree is a type of Data Structure that consists of data, a left child, and a right child. This is one of those questions which is hard to put in words but when you'll look at the code, the thinking behind it comes intuitively, still I shall try my best to break it down. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no restriction on how your serialization/deserialization algorithm should work. ![]() Question: Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. ![]() You might've used JSON.stringify and JSON.parse for storing data and retrieving data respectively. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |