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
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
Last updated