Traversal of Tree

Algorithm and explanation of Preorder , Inorder and Postorder traversal

PREORDER TRAVERSAL

Basic Logic

1. Process the root node
2. Traverse the left subtree in preorder
3. Traverse the right subtree in preorder

(Not a very useful basic logic is it , its like saying inclusion functions are inclusive 🤣, but these three lines will help to differentiate the three orders in the end, so wait a whil! )

Basically ,We are first processing all the nodes in the left. Once we hit dead end, we go back to the most recent right neighbour ( this is where stack comes to play, cause the right subtree’s addresses are stored in the stack. As stack follows the last in first out concept, we can easily access the most recently stored value). and follow the same procedure considering the right neighbour as the ‘node’. Let’s look at the algorithm to understand this better step by step.

Algorithm

• Pointer variable ‘T’ stores the root node address. S and TOP denote auxilary stack and its associated top index, respectively. The pointer variable ‘P’ denotes the current node in the tree

1. (Initialise)

If T = NULL

Then, write (‘EMPTY TREE’) — return

else TOP → 0 and call PUSH (S , TOP, T)

2. (Process each stacked branch address)

Repeat step 3 while TOP > 0

3. (Get stored address and branch left)

P < — POP (S ,TOP)

Repeat while P != NULL

write ( DATA(P))

If RPTR (P) != NULL

Then call PUSH(S,TOP,RPTR (P)) // Store address of non-empty right sub tree

P < — LPTR(P) // branch left

4. Finished — return

Explanation

Didn’t understand anything? Dont’ worry, That was my condition the first time too. Let me break it down for you.

1. If the tree is empty, then write empty and return

else, place the pointer to the root of the tree on a stack S, The TOP of the stack is updated.

2. Repeat step 3 while the stack is non-empty

3. Pop the TOP pointer off the stack and repeat while the pointer is not null.

write / process the data associated with the node.

If the right subtree is not empty then stack the pointer to the right subtree in the stack S.

Set the pointer value to the left subtree.

Recursal way

Root node address is given by pointer variable T.

function — PREORDER(T)

1. (Process the root node)

If T != NULL

then write (DATA(T))

else write (‘EMPTY TREE’)

return

2. (Process Left Subtree)

If LPTR(T) != NULL

then call PREORDER (LPTR(T))

3. (Process Right Subtree)

If RPTR(T) != NULL

then call PREORDER ( RPTR(T))

4. Return

INORDER TRAVERSAL

Basic Logic

1. Traverse the left subtree in inorder
2. Process the root node
3. Traverse the right subtree in inorder

(Notice the order difference from the first basic logic!)

In preorder, , we processed the node first — checked if that node had a left child, if it did, processed it, checked if that child had a left child, if it didn’t then we checked if it had a right child, processed that and moved back to the root node.

In inorder, we process the left ‘SUBTREE’ first, (not the node, mind you). First we check if the node has a left node or not, if it does then move pointer to the left node, keep doing this till there are not left nodes left in that path, then process the last leaf left node ( damn, this writer is on an alliteration roll today) . Now process the parent of this last leaf left node. Check if the root node has a right node, process that. If not traverse back to the parent of the parent ( grandparent) node. Continue this till all the nodes in your tree are traversed (or till you feel like climbing a tree and yelling at the world for creating DSA 🤣)

This is the most basic idea of inorder, now let us see this in algorithm form…Try to corelate the above steps with the algorithm below!

Algorithm

‘T’ is a variable which contains the address of the root of the tree

‘S’ and ‘TOP’ denote an auxiliary stack and its associated top index, respectively

The pointer variable ‘P’ denotes the current node in the tree.

1. (Initialise) — Push NULL onto stack ‘S’ and initialise pointer ‘P’

TOP = 1

S[TOP] = NULL

P = T

2. (Push leftmost path onto stack)

Repeat while P != NULL (Moving pointer to the last left node and putting the parents nodes’ address in stack — for recursal purposes)

a) TOP = TOP +1

S[TOP] = P

(b) P = LPTR (P)

3. (Pops node from stack once deadend reached)

P = S[TOP]

TOP = TOP -1

4. (Perform Backtracking)

Repeat while P!= NULL

a) Apply PROCESS to DATA(P)

b) If RPTR (P) != NULL

then P = RPTR(P)

Go to Step 2

c) P = S[TOP]

TOP = TOP -1

5. Return

Recursal Way

function — INORDER

1. (Check for empty tree)

If T = NULL

then write (‘Empty tree’)

return

2. (Process the left subtree)

If LPTR (T) != NULL

then call INORDER(LPTR(T))

3. (Process the root node)

Write (DATA(T))

4. (Process the right subtree)

If RPTR(T) != NULL

then call INORDER ( RPTR(T))

5. Return

You notice the major difference in both the traversal algorithms? In Preorder, we are going from top to down, first parents are processed then children. In inorder, because we need the children to be processed first, we are moving the pointer down first, then traversing it down to up!

POSTORDER TRAVERSAL

Basic logic

1. Traverse the left subtree in postorder
2. Traverse the right subtree in postorder
3. Process the root node.

Algorithm

This time each node will be stacked twice, once when its left subtree is traversed and once when its right subtree is traversed. On completion of these two traversals, the particular root node is processed.

Hence we need two types of stack entries, the first indicating that a left subtree is being traversed, and the second that a right subtree is being traversed.

For our convenience, we will used NEGATIVE POINTER VALUES — to indicate when right sub tree traversal, and POSITIVE POINTER VALUES — to indicate when left sub tree traversal occurs.

1. (Initialise)

If T = NULL

then write (“Empty Tree”)

return

else P = T

TOP = 0

2. (Traverse in postorder)

Repeat through 5th step while true

3. (Descend left)

Repeat while P != NULL

Call PUSH ( S,TOP,P) // store into stack

P = LPTR (P) // Move to LPTR

4. (Process a node whose left and right subtrees have been traversed)

Repeat while S[TOP] <0

P = POP (S,TOP)

Write (DATA(P))

If TOP = 0 // Have all nodes been processed>

then return

5. (Branch right and then mark node from which we branched)

P = RPTR (S[TOP])

S[TOP] = — S[TOP] // As soon as the right subtree of a particular node starts getting traversed, the sign of the node stored is set to negative

Explanation

1. If the tree is empty — then write empty tree and return, else initialise the stack and pointer value to the root of the tree.
2. Start an infinite loop to repeat through step 5
3. Repeat while pointer value is not null — Stack current pointer value, set pointer to the left subtree ( A chain of left branches is followed and the address of each node encountered is stacked)
4. Repeat while top pointer on stack is negative — Pop pointer off stack, write data associated with it ( Prints out the data associated with those nodes whose right and left subtree have been traversed.)

If stack is empty then return

5. Set pointer value to the right subtree of the value on the top of the stack. Stack the negative value of the pointer to the right subtree. (Negation occurs indicating both left and right subtrees have been traversed and that its data may be printed).

Recursal way

function — POSTORDER

1. (Check for empty tree)

If T = NULL

Then write (‘Empty tree’)

Return

2. (Process the left subtree)

If LPTR(T) != NULL

then call POSTORDER (LPTR(T))

3. (Process the right subtree)

If RPTR (T) != NULL

Then call POSTPORDER (RPTR(T))

4. (Process the root node)

Write (DATA(T))

5. Finish (Return)