Perform the depth first traversal and the breadth first traversal for the grah s

Question

Perform the depth first traversal and the breadth first traversal for the grah shown below and fill in the blanks in the following statements. Simply use comma with no spaces to write the lists:

Depth first traversal order is _______ and breadth first traversal order is _______.

Height of DFT tree is _____ and height of BFT tree is _____. Note that the height of a tree with just one node is 1.

In the DFT tree, parent of node 6 is node _____ and parent of node 5 is node _____. In the BFT tree, parent of node 6 is node _____ and parent of node 5 is node ______.

What I think?

1.) DFT is 1,2,3,4,5,6,7,8,9,10

2.) BFT is 1,2,7,10,3,4,6,9,8,5

My book is vague about the heights of depth and breadth, I get them with binary trees, but lost witht these..and the same with parent nodes? I think I've missed something simple.

Can someone help me to solve this please. :)

Explanation / Answer

1) DFT is 1,2,3,4,5,6,7,8,9,10

2) BFT is 1,2,6,7,10,3, 4, 5, 8, 9

Height of DFT tree : 5

Path from 1 to 6 (i.e 1, 2, 4, 5, 6) is the longest path in DFT tree

Note DFT tree looks like:

1

/

2 7

/ |

3 4 8

| |

5 9

| |

6 10

Height of BFT tree : 3

BFT tree:

1

/ /

2 6 7 10

/ | /

3 4 5 8 9

In BFT parent of 6: 1 and parent of 5: 6

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.