Binary Tree Traversal

Traversal is an essential operation of any data structure. It is the process of reaching out to or visiting every element stored in the data structure at least once. Unlike linear data structures where traversal can be done in only one way, a binary tree can be traversed in different ways.  Three common Binary Tree Traversal methods are

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal

Preorder Traversal

Preorder traversal is the traversal technique where the root node of a tree/subtree is processed before processing its left and right child nodes. In short the Preorder traversal can be termed as Root, Left, Right. The steps for preorder traversal are

1. Process the current node
2. Perform Preorder Traversal on the left subtree of the current node
3. Perform Preorder Traversal on the right subtree of the current node

Inorder Traversal

Inorder traversal is binary tree traversal where the root node of a tree/subtree is processed after processing its left child node but before processing the right child node. The root node is processed between the left and right child node processing. In short Inorder traversal can be termed as  Left, Root,  Right. The steps for inorder traversal are

1. Perform Inorder Traversal on the left subtree  of the current node
2. Process the current node
3. Perform Inorder Traversal on the right subtree  of the current node

Postorder Traversal

Postorder Binary tree traversal is the traversal where the root node of a tree/subtree is processed after processing its left child node and the right child node. That is the root node is processed after processing of the left and right child nodes. In short the Postorder traversal can be termed as Left, Right, Root. The steps for postorder traversal are

1. Perform Postorder Traversal on the left subtree  of the current node
2. Perform Postorder Traversal on the right subtree  of the current node
3. Process the current node

Process is a general term used in a binary tree traversal. A process can be printing the values of the nodes, evaluation of the node value, updating the node value or counting the nodes.

admin