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

Delete a given specific node from a doubly linked list. , D elete a specif...

D elete a specific Node from Double Linked List as follows DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FORW [ BACK [LOC]]:= FORW[LOC]& BACK [FORW[

Graph & optimal scheduling, You are given an undirected graph G = (V, E) in...

You are given an undirected graph G = (V, E) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight of either {1,2,...,W}, where W

Functions for inserting and deleting at either end of deque, Q. Devise a re...

Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write fu

Preorder - postorder and inorder, 1) preorder, postorder and inorder 2) ...

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

Objectives of lists, After going through this unit, you will be able to: ...

After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

A tree having ''m'' nodes has (m-1) branches. prove., Q. Prove the hypothes...

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".      Ans: A tree having m number of nodes has exactly (m-1) branches Proof: A root

Notes, Ask question #Minimum 10000 words accepted#

Ask question #Minimum 10000 words accepted#

Linked list, write an algorithm for multiplication of two sparse matrices u...

write an algorithm for multiplication of two sparse matrices using Linked Lists

Sort 5, The number of interchanges needed to sort 5, 1, 6, 2 4 in ascending...

The number of interchanges needed to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is 5

Need it urgently, Write an assembly program to separate the number of posit...

Write an assembly program to separate the number of positive numbers and negative numbers from a given series of signed numbers.

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