Traversing Binary Tree

DEFINITION

Traversing a Binary Tree means processing / visiting all the nodes of a Binary Tree once in a systematic manner. Starting from the root of a binary tree, there are three main methods that can be performed to perform tree traversal. These methods are

• Inorder Traversal
• Preorder Traversal
• Postorder Traversal

TRAVERSAL METHODS

Inorder Traversal 

To traverse a non-empty binary tree in inorder, the following operations are performed recursively
   1. Traverse the left subtree.
   2. Visit the root.
   3. Traverse the right subtree.

Algorithm

For a given binary tree let the address of root node is given by the pointer R. Let LPTR stores address if left child and RPTR stores address of right child. This algorithm recursively traverse the binary tree in  inorder

INORDER(T)
Step 1: Check for empty Tree
             IF R=NULL THEN
                  PRINT ("EMPTY TREE")
                  EXIT
            ENDIF

Step 2: Traverse Left subtree in inorder
            IF LPTR(R) < > NULL THEN
                  CALL INORDER(LPTR(R))
            ENDIF

Step 3: Process the Root
            PRINT (INFO(R))

Step 4: Traverse Right subtree in inorder
             IF RPTR(R) < > NULL THEN
                  CALL INORDER(RPTR(R))
             ENDIF

Step 5: Exit

Preorder Traversal

To traverse a non-empty binary tree in preorder, the following operations are performed recursively 
   1. Visit the root.
   2. Traverse the left subtree.
   3. Traverse the right subtree.

Algorithm

For a given binary tree let the address of root node is given by the pointer R. Let LPTR stores address if left child and RPTR stores address of right child. This algorithm recursively traverse the binary tree in  pre order

PREORDER(T)
Step 1: Check for empty Tree
             IF R< > NULL THEN
                  PRINT INFO(R)
             ELSE
                  PRINT ("EMPTY TREE")
                  EXIT
            ENDIF

Step 2: Traverse Left subtree in preorder

            IF LPTR(R) < > NULL THEN
                  CALL PREORDER(LPTR(R))
            ENDIF

Step 3: Traverse Right subtree in preorder
             IF RPTR(R) < > NULL THEN
                  CALL PREORDER(RPTR(R))
             ENDIF

Step 4: Exit

Postorder Traversal

To traverse a non-empty binary tree in postorder, the following operations are performed recursively 
   1. Traverse the left subtree.
   2. Traverse the right subtree.
   3. Visit the root.

Algorithm

For a given binary tree let the address of root node is given by the pointer R. Let LPTR stores address if left child and RPTR stores address of right child. This algorithm recursively traverse the binary tree in  postorder

POSTORDER(T)
Step 1: Check for empty Tree
             IF R=NULL THEN
                  PRINT ("EMPTY TREE")
                  EXIT
            ENDIF

Step 2: Traverse Left subtree in postorder

            IF LPTR(R) < > NULL THEN
                  CALL POSTORDER(LPTR(R))
            ENDIF

Step 3: Traverse Right subtree in postorder
             IF RPTR(R) < > NULL THEN
                  CALL POSTORDER(RPTR(R))
             ENDIF


Step 4: Process the Root
            PRINT (INFO(R))


Step 5: Exit