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
This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

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

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part

Q. What do you mean by the best case complexity of quick sort and outline why it is so. How would its worst case behaviour arise?

What do we mean by algorithm? What are the characteristics of a good and relevant algorithm? An algorithm is "a step-by-step procedure for finishing some task'' An algorithm c

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

Define Prim's Algorithm Prim's  algorithm  is  a  greedy  algorithm  for  constructing  a  minimum  spanning  tree  of  a  weighted linked graph. It works by attaching to a bef