types of traversals in a binary tree
October 8, 2012 Leave a comment
There are three types of traversals in binary tree: pre-order, in-order and post-order
Lets take an example of BST
20
15 25
12 18 22 28
pre-order: visit each node before its children
public void preorder(BinaryNode root) {
if(root != null) {
System.out.println(root.element);
preorder(root.left);
preorder(root.right);
}
}
Output: 20, 15, 12, 18, 25, 22, 28
in-order (applied only for binary trees): visit left sub-tree, node and then right sub-tree
public void inorder(BinaryNode root) {
if(root != null) {
inorder(root.left);
System.out.println(root.element);
inorder(root.right);
}
}
Output: 12, 15, 18, 20, 22, 25, 28
Note: If we notice the above elements they are all sorted which means the inorder traversal of any BST gives us the sorted elements.
post-order: visit each node after its children (left and right sub trees)
public void postorder(BinaryNode root) {
if(root != null) {
postorder(root.left);
postorder(root.right);
System.out.println(root.element);
}
}
Output: 12, 18, 15, 22, 28, 25, 20
coding algorithms 
Recent Comments