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

How does an array differ from an ordinary variable, Normal 0 fa...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

What is Polyphase Sort, One of the best known methods for external sorting ...

One of the best known methods for external sorting on tapes is the polyphase sort. Principle: The basic strategy of this sort is to distribute ordered initial runs of predetermi

Binary search trees, In this unit, we discussed Binary Search Trees, AVL tr...

In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Algorithm to find maximum and minimum numbers, Give an algorithm to find bo...

Give an algorithm to find both the maximum and minimum of 380 distinct numbers that uses at most 568 comparisons.

Threaded binary tree, i need the full concept of it... please can anyone pr...

i need the full concept of it... please can anyone provide

Graph, adjacency multilist

adjacency multilist

What is solid modeling, What is Solid modeling Solid modeling is the mo...

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

Size of stack, The size of stack was declared as ten. Thus, stack cannot ho...

The size of stack was declared as ten. Thus, stack cannot hold more than ten elements. The major operations which can be performed onto a stack are push and pop. However, in a prog

Hw7, Handout 15 COMP 264: Introduction to Computer Systems (Section 001) Sp...

Handout 15 COMP 264: Introduction to Computer Systems (Section 001) Spring 2013 R. I. Greenberg Computer Science Department Loyola University Water TowerCampus, Lewis Towers 524 82

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

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