How to construct binary tree, Data Structure & Algorithms

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.

1511_binary tree1.png

 

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







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
Related Questions
c++ To calculate the amount to be paid by a customer buying yummy cupcakes for his birth day party

In this unit, the following four advanced data structures have been practically emphasized. These may be considered as alternative to a height balanced tree, i.e., AVL tree.

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o

Insertion & deletion of target key requires splaying of the tree. In case of insertion, the tree is splayed to find the target. If, target key is found out, then we have a duplicat

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Method to measure address of any element of a matrix stored in memory. Let us consider 2 dimensional array a of size m*n further consider that the lower bound for the row index


Queue is a linear data structure utilized in several applications of computer science. Such as people stand in a queue to get a specific service, several processes will wait in a q

Q. Create a heap with the given list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12                                                  Ans: Creation