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
Implementation of queue using a singly linked list: While implementing a queue as a single liked list, a queue q consists of a list and two pointers, q.front and q.rear.

Time Complexity, Big O notation The amount of time needed by an algorithm to run to its completion is referred as time complexity. The asymptotic running time of an algorithm i

Declaring a two dimensional array   A two dimensional array is declared same to the way we declare a one-dimensional array except that we state the number of elements in both di


Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

compare and contrast the bubble sort,quick sort,merge sort and radix sort

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

Let a be a well-formed formula. Let c be the number of binary logical operators in a. (Recall that ?, ?, ?, and ? are the binary logical operators). Let s be the number of proposit

Link list representation of a circular queue is more efficient as it employs space more competently, of course with the added cost of storing the pointers. Program 7 gives the link

How to creat ATM project by using double linked list?