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
Which are the two standard ways of traversing a graph? i. The depth-first traversal   ii. The breadth-first traversal

Q. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (

Q. Describe the term array.  How do we represent two-dimensional arrays in memory?  Explain how we calculate the address of an element in a two dimensional array.

Develop a program that accepts the car registration( hint: LEA 43242010)

calculate gpa using an algorithm

Q. How can we free the memory by using Boundary tag method in the context of Dynamic memory management?

Give the example of bubble sort algorithm For example List: - 7 4 5 3 1. 7 and 4 are compared 2. Since 4 3. The content of 7 is now stored in the variable which was h

Z-Buffer Algorithm Also known as the Depth-Buffer algorithm, this image-space method simply selects for  display the polygon or portion of a polygon that is nearest to the view

Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know