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
write a pseudocode to input the top speed (in km''s/hours) of 5000 cars output the fastest speed and the slowest speed output the average (mean) speed of all the 5000 cars answers

Write the algorithm for compound interest

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Explain the Arrays in Ruby Ruby arrays are dynamic arrays which expand automatically whenever a value is stored in a location beyond current end of the array. To the programmer

Illustrates the program for Binary Search. Program: Binary Search /*Header Files*/ #include #include /*Functions*/ void binary_search(int array[ ], int value,

Explain how two dimensional arrays are represented in memory. Representation of two-dimensional arrays in memory:- Let grades be a 2-D array as grades [3][4]. The array will

what''s queue ?

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

how to reduce the number of passes in selection sort

Question 1. How can you find out the end of a String? Write an algorithm to find out the substring of a string. 2. Explain the insertion and deletion operation of linked lis