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
Explain what are circular queues? Write down routines required for inserting and deleting elements from a circular queue implemented using arrays.           Circular queue:

Memory Allocation Strategies If it is not desirable to move blocks of due storage from one area of memory to another, it must be possible to relocate memory blocks that have be


I need a person who has a good background in using R. Studio? In adition, a person who is good in using algorithms.

Program: Program segment for insertion of an element into the queue add(int value) { struct queue *new; new = (struct queue*)malloc(sizeof(queue)); new->value = val

The information in the table below is available for a large fund-raising project. a. Determine the critical path and the expected completion time of the project. b. Plot the total

Operation of Algorithm The following sequence of diagrams shows the operation of Dijkstra's Algorithm. The bold vertices show the vertex to which shortest path has been find ou

what are registers? why we need register? Definition? Types? What registers can do for us?

compare two functions n and 2n for various values of n. determine when second becomes larger than first

Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position