Binary Tree Traversal

In-order (root second) , Pre-order (root first) , Post-order (root last) & Level-order Traversal

• The process of visiting all nodes of a tree is called tree traversal

• Traversing a binary tree requires traversal of each component

  • Processing root node

  • traversing the left subtree

  • traversing the right subtree

Sometimes reverse traversals also helps to solve several binary tree coding problems.

Morris In-order Traversal (root second)

Traverse from the left subtree to the root then to the right subtree.

In the inorder traversal, the root is visited after visiting its left subtree but before visiting the right subtree.

void inOrderTraversal(Node root)
{
  if (root == null)return;
  
  inOrderTraversal(root.left);
  System.out.println(root.name);
  inOrderTraversal(root.right);
}

Use cases

• In a binary search tree to get the nodes in non-decreasing order

Pre-order Traversal (root first)

In the preorder traversal, the root is visited before the left and right subtrees are visited (in that order).

void preOrderTraversal(Node root)
{
  if (root == null)return;
  
  System.out.println(root.name);
  inOrderTraversal(root.left);
  inOrderTraversal(root.right);
}

Usecase

• To explore the root before the leaves

• To get get prefix expression of the tree

Post-order Traversal (root last)

First process all nodes in the left subtree, then process all nodes in the right subtree, and at the end, we process the root node.

In the postorder traversal, the root is visited after visiting the left and right subtrees (in that order).

void postOrderTraversal(Node root)
{
  if (root == null)return;
  
  inOrderTraversal(root.left);
  inOrderTraversal(root.right);
  System.out.println(root.name);
}

Usecase

• For deleting the entire binary tree

• To get the post-fix expression of the tree

Level-order Traversal (BFS)

Start by processing the root node, then process all nodes at the first level, second level, and so on.

Explore all nodes at the current level before moving on to nodes at the next level.

References

• Binary tree traversal

• Recursive Binary Tree Traversals: Preorder, Inorder and Postorder

• Level Order (Breadth First Search) Traversal of Binary Tree