Tree traversal, Data Structure & Algorithms

Assignment Help:

Q. What do you understand by the tree traversal? Write down the procedure for traversing a binary tree in preorder and execute it on the following tree. 

419_tree traversal.png

 

Ans:

The algorithm walks through tree data structure and performs some calculation at each node in the tree. This procedure of walking through the tree is called a tree traversal.

There are basically two different methods in which to visit systematically all the nodes of a tree-the depth-first traversal and the breadth-first traversal. Certain depth- first traversal methods happen frequently enough that they are given names of their own: preorder traversal, inorder traversal and postorder traversal.

The algorithm for traversing a tree in preorder is written as follows:-

i.     Process the root R.

ii.    Traverse left sub tree of R in preorder.
iii.   Traverse right sub tree of R in preorder. The preorder for the given tree is as follows:-

A   L1  R1

A  B    L1l  L1R  R1

A  B    D      L1R  R1

A  B    D      E       R1

A  B    D      E       C    R1L  R1R

A  B      D         E            C      F       R1R

A  B          D         E          C            F       G


Related Discussions:- Tree traversal

#title.state charts., explain two strategies to implement state charts with...

explain two strategies to implement state charts with the help of an example of each.

Using array to execute the queue structure, Q. Using array to execute the q...

Q. Using array to execute the queue structure, write down an algorithm/program to (i) Insert an element in the queue. (ii) Delete an element from the queue.

Implement stack using two queues, How To implement stack using two queues ,...

How To implement stack using two queues , analyze the running time of the stack operations ?

Recursion, differences between direct and indirect recursion

differences between direct and indirect recursion

Determine the critical path and the expected completion, The information in...

The information in the table below is available for a large fund-raising project. a. Determine the critical path and the expected completion time of the project. b. Plot the total

Define an array, Define an array. Array is made up of same data structu...

Define an array. Array is made up of same data structure that exists in any language. Array is set of same data types. Array is the collection of same elements. These same elem

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke...

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

What is bubble sort, What is bubble sort? Bubble Sort: The basic ide...

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

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

Algorithm, implement multiple stacks in a single dimensional array. write a...

implement multiple stacks in a single dimensional array. write algorithm for various stack operation for them

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