Algorithm to build a binary tree , Data Structure & Algorithms

Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.                                                                                                                          

Ans.

Tree cannot be built using the Preorder and Postorder traversal of the binary

tree. For this Inorder traversal has to be given to us.

Hence to construct a tree using Inorder and preorder traversal (as an example, traversals of Q 104 are used), the algorithm is stated follows:

The tree T is drawn from the root in the downward direction as follows:

1)     The root of T is obtained by selecting the first node in its preorder. Hence G is the root of the node.

2) The left child of the node G is obtained as by. First using the inorder of T to find the node in the left subtree LTA  of G. Thus LTA comprises of the nodes B,Q,A,C,K,F. Then the left child of G is obtained by selecting the first node in the preorder of LTA (which appears in the Preorder of T). Hence B is the left son of G.

3)     Likewise the right subtree RTA of G comprises of the nodes P, D, E, R, H and P is the root of RTA, which means P is the right child of G.

Repeating the above steps with the each new node, we finally get the required tree.

 

 

Posted Date: 7/12/2012 8:38:46 AM | Location : United States







Related Discussions:- Algorithm to build a binary tree , Assignment Help, Ask Question on Algorithm to build a binary tree , Get Answer, Expert's Help, Algorithm to build a binary tree Discussions

Write discussion on Algorithm to build a binary tree
Your posts are moderated
Related Questions
i:=1 while(i { x:=x+1; i:=i+1; }

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

#What is the pointer

What are the Dynamic arrays Dynamic arrays are convenient for programmers since they can never be too small-whenever more space is needed in a dynamic array, it can simply be e

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

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

* Initialise d & pi* for each vertex v within V( g ) g.d[v] := infinity  g.pi[v] := nil g.d[s] := 0; * Set S to empty * S := { 0 }  Q := V(g) * While (V-S)

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo

For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the po