Tree traversal is a process of visiting each node in a tree exactly once. Unlike linear data structures such as array and linked list which is canonically traversed in linear order, a tree may be traversed in depth-first or breadth-first order

### Depth First Traversal

There are 3 ways of depth-first traversal, typically, classified by the orders in which nodes are visited

• Pre-order visits the parent node before all traversal to the left and the right subtree
• In-order visits the parent node between traversal to the left and the right subtree
• Post-order visits the parent node after all traversal to the left and the right subtree

Depth-first traversal orders for the above tree

• Pre-oder is 7-2-1-3-9
• In-order is 1-2-3-7-9
• Post-oder is 1-3-2-9-7

## Implementation example with Recursive algorithm

``````
``````

## Implementation example with Iterative algorithm

Approach

• Using a stack to track which node to visit next
``````
``````

`BSTByLinkedList` is defined in Binary Search Tree Data Structure