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.                                                                                                                          


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 program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

multilist representation of graph

1. Apply the variant Breadth-First Search algorithm as shown in Figure 2 to the attached graph. This variant is used for computing the shortest distance to each vertex from the sta

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Deletion in a RBT uses two main processes, namely, Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in

Q. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine.    A n

What is Ruby Ruby has numerous simple types, including numeric classes such as Integer, Fixnum, Bignum, Float, Big Decimal, Rational, and Complex, textual classes like String,

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as