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

Find the complexity of an algorithm, Q.1 What is an algorithm? What are the... Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

Explain the different types of traversal on binary tree, Question 1 What i... Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

Stack, Explain the array and linked list implementation of stack Explain the array and linked list implementation of stack

Binary tree and binarytree parts, Q. What do you understand by the term Bin... Q. What do you understand by the term Binary Tree? What is the maximum number of nodes which are possible in a Binary Tree of depth d. Explain the terms given below with respect to

Entity relationship diagram, This question is based on the requirements of ... This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Consistent heuristic function - graph search, Consistent Heuristic Function... Consistent Heuristic Function - Graph Search Recall the notions of consistency and admissibility for an A* search heuristic. a. Consider a graph with four nodes S, A, B, C,

Define doubly linked list, A list item stores pointers and an element ... A list item stores pointers and an element to predecessor and successor. We call a pointer to a list item a handle . This looks simple enough, but pointers are so powerful tha

How can a lock object be called in the transaction, How can a lock object b... How can a lock object be called in the transaction? By calling Enqueue and Dequeue in the transaction.

Complete trees, This is a k-ary position tree wherein all levels are filled... This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

Explain Hashing, What do you mean by hashing? Hashing gives the direct ... What do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func