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
Q. Let a binary tree 'T' be in memory. Write a procedure to delete all terminal nodes of the tree.       A n s . fun ction to Delete Terminal Nodes from Binary Tree

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam


Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

Q.1 Compare two functions n 2 and 2 n for various values of n. Determine when second becomes larger than first. Q.2 Why do we use asymptotic notation in the study of algorit

Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.

In a circular linked list There is no beginning and no end.

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

write a COBOL program to find the biggest of two numbers