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

Binary search, An unsorted array is searched through linear search that sca... An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found. The cause for sorting an array is that we search

Flowcharts, draw a flowchart which prints all the even numbers between 1-50... draw a flowchart which prints all the even numbers between 1-50

Explain best - fit method, Best - Fit Method: - This method obtains the sma... Best - Fit Method: - This method obtains the smallest free block whose  size is greater than or equal to get such a block by traversing the whole free list follows.

Examination, Write an algorithm for binary search. What are its limitations... Write an algorithm for binary search. What are its limitations? .

Physical database design and sql queries, In this part, students are allowe... In this part, students are allowed to implement the following simplifications in their table and data design. o Availability for the beauty therapists don't have to be considere

Applications of borazole, Ask question #Minimum 1cepted# Ask question #Minimum 1cepted#

Array, how to define the size of array how to define the size of array

Algorithm to sort a given list by quick sort method, Q. Write down an algor... Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Representation of max-heap sequentially, Q. How do we represent a max-heap ... Q. How do we represent a max-heap sequentially? Explain by taking a valid   example.         Ans: A max heap is also called as a descending heap, of size n is an almos

Cohen sutherland algorithm, Using the cohen sutherland. Algorithm. Find the... Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)