Given the preorder and inorder traversals of a binary tree with n nodes, what wo
ID: 3685659 • Letter: G
Question
Given the preorder and inorder traversals of a binary tree with n nodes, what would be the worst case big O running time to build the tree...
a) Given the preorder and inorder traversals of a binary tree with n nodes, what would be the worst case big O running time to build the tree, counting only comparisons between items in the preorder and inorder traversals toward the running time? Clearly show your derivation with explanation of the steps, otherwise you will not get any credit b) After an AVL tree insertion, when walking back up toward the root, a node x is found to be unbalanced. Further, it is determined that x's balance factor is the same as that of the root, q of its taller subtree (Case 1). Complete the following rotateCasel method to perform the required rotation to rebalance the tree at node x. public class AVLTreeNodeT extends ComparableT>> public T data; public AVLTreeNode left, right public char balanceFactor 1/'-or '/' or' public AVLTreeNode parent; public int height; // returns the root of the updated tree public staticExplanation / Answer
The above problem can be solved recursively.
The first thing you have to assume is that there are no duplicates in your binary tree so that we can clearly see ambiguity of same solutions in both preorder or inorder traversals.
_______ 15 ______
/
__18__ ___10
/ /
12 11 16 _
/
9 19
The inorder traversal of above binary tree is {12,18,11,9,15,19,16,10}
The preorder traversal of above binary tree is { 15,18,12,11,9,10,16,19}
tree’s root always coincides with the first element in preorder traversal. This is true because in preorder traversal you always traverse the root node before its children. The root node’s value appear to be 15 from the binary tree above.
We easily find that 15 appears as the 4th index in the inorder sequence. For inorder traversal, we visit the left subtree first, then root node, and followed by the right subtree. Therefore, all elements left of 15 must be in the left subtree and all elements to the right must be in the right subtree.
A recursive pattern can be seen from above point.
After creating the root node (15), we construct its left and right subtree from inorder traversal of {12,11,18,9} and {10,16,19} respectively. We also need its corresponding preorder traversal which could be found in a similar fashion. If you remember, preorder traversal follows the sequence of root node, left subtree and followed by right subtree. Therefore, the left and right subtree’s postorder traversal must be {18,12,11,9} and {10,16,19} respectively. Since the left and right subtree are binary trees in their own right, we can solve recursively.
we search the root value’s index in the inorder sequence.so constructed binary tree can be left/right skewed so it takes the time complexity of O(n^2).
Note: A more efficient way is to eliminate the search by using an efficient look-up mechanism such as hash table. By hashing an element’s value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(N) time to construct the tree, which theoretically is the most efficient way.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.