Algorithm to build a binary tree , Data Structure & Algorithms

Assignment Help:

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.

 

 


Related Discussions:- Algorithm to build a binary tree

The best average behaviour, The best average behaviour is shown by  Qui...

The best average behaviour is shown by  Quick Sort

State hsv colour model, HSV Colour Model Instead of a set of colour pri...

HSV Colour Model Instead of a set of colour primaries, the HSV model uses colour descriptions that have a more intuitive appeal to a user. To give a colour specification, a use

Determine in brief the painter algorithm, Determine in brief the Painter A...

Determine in brief the Painter Algorithm a) The farthest polygon, namely the rectangle PQRS, is stored first. (b) The next farthest, the quadrilateral ABCD, is superpo

Search on a heap file, Consider the file " search_2013 ". This is a text fi...

Consider the file " search_2013 ". This is a text file containingsearch key values; each entry is a particular ID (in the schema given above). You are tosimulate searching over a h

Briefly explain the prim''s algorithm, Question 1 Describe the following- ...

Question 1 Describe the following- Well known Sorting Algorithms Divide and Conquer Techniques Question 2 Describe in your own words the different asymptotic func

Registers, what are registers? why we need register? Definition? Types? Wha...

what are registers? why we need register? Definition? Types? What registers can do for us?

Algorithms, write short note on algorithms

write short note on algorithms

Define midsquare method, Midsquare Method :- this operates in 2 steps. In t...

Midsquare Method :- this operates in 2 steps. In the first step the square of the key value K is taken. In the 2nd step, the hash value is obtained by deleting digits from ends of

Write the algorithm of the quick sort, Ans. An algorithm for the quick...

Ans. An algorithm for the quick sort is as follows: void quicksort ( int a[ ], int lower, int upper ) { int i ; if ( upper > lower ) { i = split ( a, lower, up

Union & intersection of two linklist, how to write an algorithm for unions ...

how to write an algorithm for unions & intersection of two linklists?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd