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

Dynamic programming., Count Scorecards(30 points) In a tournament, N playe... Count Scorecards(30 points) In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a

Data Structure, Ask consider the file name cars.text each line in the file ... Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Explain multidimensional array, Multidimensional array: Multidimensional a... Multidimensional array: Multidimensional arrays can be defined as "arrays of arrays". For example, a bidimensional array can be imagined as a bidimensional table made of elements,

Binary search tree, write an algorithm to delete an element x from binary... write an algorithm to delete an element x from binary search with time complex

Single pointer pointing to the tail of the queue, Can a Queue be shown by c... Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

Red-black tree after insertion, The above 3 cases are also considered conve... The above 3 cases are also considered conversely while the parent of Z is to the right of its own parent. All the different kind of cases can be illustrated through an instance. Le

Bubble sort, In this sorting algorithm, multiple swapping occurs in one pas... In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

Properties of a red-black tree, Any binary search tree must contain followi... Any binary search tree must contain following properties to be called as a red-black tree. 1. Each node of a tree should be either red or black. 2. The root node is always bl

A linear list of elements in which deletion can be done, A linear list of e... A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

Recursion, i need help in java recursion assignment. i need help in java recursion assignment.