Algorithm to build a binary tree , Data Structure & Algorithms

Assignment Help:

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.

 

 


Related Discussions:- Algorithm to build a binary tree

Postfix expression, Ask question Write an algorithm for the evaluation of a...

Ask question Write an algorithm for the evaluation of a postfix expression using a stack#Minimum 100 words accepted#

Boar corloring, Board coloring , C/C++ Programming

Board coloring , C/C++ Programming

Design a binary tree, (a) Suppose that t is a binary tree of integers (that...

(a) Suppose that t is a binary tree of integers (that is, an object of type BinTree of Int.) in the state shown in Figure 3.   Give the vectors returned by each of the f

Mathematical-model with a collection of operations, A mathematical-model wi...

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

Test whether a binary tree is a binary search tree, Q. Write down an algori...

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

The theta-notation, This notation bounds a function to in constant factors....

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

Hash function, Q. Define the graph, adjacency matrix, adjacency list, hash ...

Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.

Difference between prism''s and kruskal''s algorithm, Difference among Pris...

Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd