Stack

Traverse tree using Depth-First traversal.

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 reversed