Tree traversal, Data Structure & Algorithms

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

Posted Date: 7/11/2012 1:38:53 AM | Location : United States







Related Discussions:- Tree traversal, Assignment Help, Ask Question on Tree traversal, Get Answer, Expert's Help, Tree traversal Discussions

Write discussion on Tree traversal
Your posts are moderated
Related Questions
(a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c


Q. Perform implementation of a queue using a singly linked list L. The operations INSER and DELETE should take O (1) time.

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Area Subdivision Method In this method, the viewport is examined for clear decisions on the polygons situated in it, in regard to their overlap and visibility to the viewer. Fo

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

The disadvantages or limitations of the last in first out costing method are: The election of last in first out for income tax purposes is binding for all subsequent yea

Pre-order Traversal The method of doing a pre-order traversal iteratively then has the several steps(suppose that a stack is available to hold pointers to the appropriate nodes

A Sort which relatively passes by a list to exchange the first element with any element less than it and then repeats with a new first element is called as      Quick sort.

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi