Queue

Traverse tree using Breath-First and Depth-First traversals.

Implement breath-first traversal - visit every node on a level before going to a lower level.

Test: breath first traverse breath first

Implement depth-first traversal. There 3 variants of depth first traversal that differ when the current node is traversed.

• Pre order - visit the node first
• In order - visit the node after traversing entire left side
• Post order - visit the node after traversing entire left side and entire right side

Algorithm:

• Visit the node
• Traverse entire left side
• Traverse entire right side

Result: F B A D C E G I H

Test: traverse depth first pre order

Algorithm:

• Traverse entire left side
• Visit the node
• Traverse entire right side

Result: A B C D E F G H I

Test: traverse depth first in order

Algorithm:

• Traverse entire left side
• Traverse entire right side
• Visit the node

Result: A C E D B H I G F

Test: traverse depth first pre order reversed

Algorithm:

• Visit the node
• Traverse entire right side
• Traverse entire left side

Result: F G I H B D E C A

Test: traverse depth first pre order reversed

Algorithm:

• Traverse entire right side
• Visit the node
• Traverse entire left side

Result: I H G F E D C B A

Test: traverse depth first in order reversed

Algorithm:

• Traverse entire right side
• Traverse entire left side
• Visit the node

Result: H I G E C D A B F

Test: traverse depth first pre order