In this tutorial, you will learn the Tree Traversal implementation example with Depth First Search

Tree Traversal

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 are canonically traversed in linear order, 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