Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes:

Inorder :          E     A    C    K    F     H    D    B    G

Preorder:         F     A    E    K    C    D    H    G    B

Draw the particular tree. Explain your algorithm as well.

Ans.

Inorder:        E     A     C     K     F     H     D     B     G

Preorder:     F     A     E     K     C     D     H     G     B

The tree T is drawn from its root downward as shown below.

a)      The root T is obtained by selecting the first node in its preorder. Therefore, F is the root of T.

b)      The left child of the node F is obtained as shown here. First use the inorder of T to find the nodes the in the left subtree T1 of F. Thus T1 consists of the nodes E, A, C and K. Then the left child of F is obtained by choosing the first node in the preorder of T1 (which appears in the preorder of T). Therefore A is the left son of F.

c)     Likewise, the right subtree T2 of F comprises of the nodes H, D, B and G, and D is the root of T2, that is, D is the right child of F.

Performing the above process with each new node, we finally obtain the desired tree.

 

Posted Date: 7/13/2012 3:06:13 AM | Location : United States

Ask an Expert

Related Discussions:- How to construct binary tree, Assignment Help, Ask Question on How to construct binary tree, Get Answer, Expert's Help, How to construct binary tree Discussions

Write discussion on How to construct binary tree
Your posts are moderated

Write your message here..

Related Questions

Balance tree, what is a balance tree? what is a balance tree?

Algorithms, b) The user will roll two (six-sided) dices and the user will l... b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

Execute algorithm to convert infix into post fix expression, Q. Execute you... Q. Execute your algorithm to convert the infix expression to the post fix expression with the given infix expression as input Q = [(A + B)/(C + D) ↑ (E / F)]+ (G + H)/ I

Write an algorithm to find outputs number of cars, A company is carrying ou... A company is carrying out a survey by observing traffic at a road junction. Every time a car, bus or lorry passed by road junction it was noted down. 10 000 vehicles were counted d

Basic datastructures, sample infosys campusconnect questions sample infosys campusconnect questions

Process of channel access, Channel access In first generation systems, ... Channel access In first generation systems, every cell supports a number of channels. At any given time a channel is allocated to only one user. Second generation systems also

Write an algorithm to measure daily temperatures, A geography class decide ... A geography class decide to measure daily temperatures and hours of sunshine each day over a 12 month period (365 days) Write an algorithm, using a flowchart that inputs tempera

Deletion of any element from the circular queue, Algorithm for deletion of ... Algorithm for deletion of any element from the circular queue: Step-1: If queue is empty then say "queue is empty" & quit; else continue Step-2: Delete the "front" element

Relation of time and space complexities of an algorithm, What is complexity... What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

Enumerate about the concept of container, Enumerate about the concept of co... Enumerate about the concept of container A Container can have a size() operation. We can also ask (somewhat redundantly) whether a Container is empty. And even though a Contain