Binary Tree Traversal

Traversal of a tree means stepping through the nodes of a tree by means of the connections between parents and children, which is also called walking the tree.

There are many operations that are often performed on a tree such as search a node, print some information, insert a node, delete a node, and so on. All such operations need the traversal through a tree.

There are several traversal methods such as

            i) Inorder traversal

            ii) Postorder traversal

            iii) Preorder traversal

Inorder Traversal

In this traversal, the left subtree is visited first in inorder followed by the root and then the right subtree in inorder.

Algorithm

1. Traverse the left subtree of the root node in inorder.

2. Visit the root node node.

3. Traverse the right subtree of the root node in inorder.

Postorder Traversal

In this traversal, the left subtree is visited first in postorder followed by the right subtree

in postorder and then the root.

Algorithm

1. Traverse the root’s left child (subtree) of the root node in postorder.

2. Traverse the root’s right child (subtree) of the root node in postorder.

3. Visit the root node.

Preorder Traversal

In this traversal, the root is visited first followed by the left subtree in preorder and then the right subtree in preorder.

Algorithm

1. Visit the root node, say D.

2. Traverse the left subtree of the node in preorder.

3. Traverse the right subtree of the node in preorder.