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

Name the five popular hashing functions, Five popular hashing functions are... Five popular hashing functions are as follows: 1) Division Method 2) Midsquare Method 3) Folding Method 4) Multiplicative method 5) Digit Analysis

Relative and direct files, Each data record contains a fixed place in a rel... Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

Define order of growth, Define order of growth The  efficiency  analysi... Define order of growth The  efficiency  analysis  framework  concentrates   on  the  order  of  growth  of  an  algorithm's   basic operation count as the principal indicator o

Merge sort, #question. merging 4 sorted files containing 50,10,25,15 record... #question. merging 4 sorted files containing 50,10,25,15 records will take time?

What is assertions and abstract data types, Assertions and Abstract Data Ty... Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

Grounded header link list and a circular header link list, What is the diff... What is the difference between a grounded header link list and a circular header link list? A header linked list is a linked list which always having a special node, known as t

Define heap, HEAP  A heap is described to be a binary tree with a key i... HEAP  A heap is described to be a binary tree with a key in every node, such that  1-All the leaves of the tree are on 2 adjacent levels. 2- All leaves on the lowest leve

Various passes of bubble sort, Q. Show the various passes of bubble sort on... Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

Which of the sorting algorithm is stable, Which of the sorting algorithm is... Which of the sorting algorithm is stable   Heap sorting is stable.

Algorithms, write short note on algorithms write short note on algorithms