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

Program segment for All pairs shortest paths algorithm AllPairsShortestPaths(int N, Matrix C, Matrix P, Matrix D) { int i, j, k if i = j then C[i][j] = 0  for ( i =

Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

Conceptually, the stack abstract data type mimics the information kept into a pile on a desk. Informally, first we consider a material on a desk, where we might keep separate stack

A small shop sells 280 different items. Every item is identified by a 3 - digit code. All items which start with a zero (0) are cards, all items which start with a one (1) are swee

Simulation of queues: Simulation is the process of forming an abstract model of a real world situation in order to understand the effect of modifications and the effect of introdu

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f