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



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
The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

A tree is a non-empty set one component of which is designated the root of the tree while the remaining components are partitioned into non-empty groups each of which is a subtree

Best Case: If the list is sorted already then A[i] T (n) = c1n + c2 (n -1) + c3(n -1) + c4 (n -1)  = O (n), which indicates that the time complexity is linear. Worst Case:

Q. Write down the recursive function to count the number of the nodes in the binary tree.    A n s . R ecursive Function to count no. of Nodes in Binary Tree is writt

Asktypes of pipelining question #Minimum 100 words accepted#

what is the difference between data type and abstract data type

Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.

What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

A telephone directory having n = 10 records and Name field as key. Let us assume that the names are stored in array 'm' i.e. m(0) to m(9) and the search has to be made for name "X"

A full binary tree with n leaves have:- 2n -1 nodes.