Given the definition of the string \"data\", below, show how the character infor
ID: 3773372 • Letter: G
Question
Given the definition of the string "data", below, show how the character information can be put into a Binary Search Tree. Then prepare the tree for transmission using a PostOrder traversal. Recreate the tree from the PostOrder information. Using an in-order traversal, sort the information. Finally, list how many letter comparisons a computer searching the tree for the letter 'S' would need to perform (how many nodes need to be searched). data = "APRUNVB" Given the corresponding BINARY SEARCH TREE for "data" below What is the PostOrder traversal of the "data" search tree? How many letter comparisons does a computer searching the tree for the letter 'S' need to perform? If you are unsure, list the order of traversal, visiting each comparison node, in your answer.Explanation / Answer
Given the data in post order traversal = APRUNVB.
The Binary tree for the above post order traversal is:
The post order traversal is based on three steps:
traverse the left subtree post order
traverse the right subtree post order
process the node
The given binary search tree is as shown below:
If the data=APRUNVB is inserted at appropriate positions then the tree is as follows:
The node at position 1 is A.
The node at position 2 is B.
The node at position 3 is P.
The node at position 4 is V.
The nodes at position 5 is N.
The node at position 6 is U.
The node at position 7 is R.
Sorting the nodes of the tree in order: A B N P R U V.
After sorting the tree is transformed as:
Searching for a letter S in the tree:
In the tree above, it requires 6 comparasions to know that the ltter S is not found in the binary search tree.
First, the letter S is compared with A. As A<S, proceedthrough the right subtree.
Next, the letter S is compared with B. As B<S, proceedthrough the right subtree.
Next, the letter S is compared with N. As N<S, proceedthrough the right subtree.
Next, the letter S is compared with P. As P<S, proceedthrough the right subtree.
Next, the letter S is compared with R. As R<S, proceedthrough the right subtree.
Next, the letter S is compared with U. As U>S, proceedthrough the left subtree.
As there is no left subtree, the search stops.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.