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

Array implementation of a multiqueue, Program gives the program segment by ...

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

Execute algorithm to convert infix into post fix expression, Q. Execute you...

Q. Execute your algorithm to convert the infix expression to the post fix expression with the given infix expression as input Q = [(A + B)/(C + D) ↑ (E / F)]+ (G + H)/ I

Quick sort method, Q. Explain quick sort? Sort the given array using quick ...

Q. Explain quick sort? Sort the given array using quick sort method. 24 56 47 35 10 90 82 31

Draw a b-tree., Q. Draw a B-tree of order 3 for the sequence of keys writte...

Q. Draw a B-tree of order 3 for the sequence of keys written below: 2, 4, 9, 8, 7, 6, 3, 1, 5, 10

Trees, Have you ever thought about the handling of our files in operating s...

Have you ever thought about the handling of our files in operating system? Why do we contain a hierarchical file system? How do files saved & deleted under hierarchical directories

Search on a heap file, Consider the file " search_2013 ". This is a text fi...

Consider the file " search_2013 ". This is a text file containingsearch key values; each entry is a particular ID (in the schema given above). You are tosimulate searching over a h

Define ordinary variable, Ordinary variable An ordinary variable of a e...

Ordinary variable An ordinary variable of a easy data type can store a one element only

Applications of linear and binary search, The searching method are applicab...

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

Number of leaf nodes in a complete binary tree, The number of leaf nodes in...

The number of leaf nodes in a complete binary tree of depth d is    2 d

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