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
How sparse matrix stored in the memory of a computer?

The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write

Board coloring , C/C++ Programming

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Q. Write down an algorithm to insert a node in between any two nodes in a linked list         Ans. Insertion of a the node after the given element of the listis as follows

Write an algorithm, using a flowchart, which inputs the heights of all 500 students and outputs the height of the tallest person and the shortest p erson in the school.

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

A binary tree is a tree data structures in which each node have at most two child nodes, generally distinguished as "right" and "left". Nodes with children are called parent nodes,

#questWrite an algorithm for multiplication of two sparse matrices using Linked Lists.ion..