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 an algorithm for multiplication of two sparse matrices using Linked Lists

An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Q. Write down a non recursive algorithm to traverse a binary tree in order.                    Ans: N on - recursive algorithm to traverse a binary tree in inorder is as

A geography class decide to measure daily temperatures and hours of sunshine each day over a 12 month period (365 days) Write an algorithm, using a flowchart that inputs tempera

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Range: A Structured Type in Ruby Ruby has a numerous structured types, comprising arrays, hashes, sets, classes, streams, and ranges. In this section we would only discuss rang

A spanning tree of any graph is only a subgraph that keeps all the vertices and is a tree (having no cycle). A graph might have many spanning trees. Figure: A Graph

Red-Black trees have introduced a new property in the binary search tree that means an extra property of color (red, black). However, as these trees grow, in their operations such