Hierarchical Datastructure – Tree Traversals

Introduction

This is the first article in the Tree Traversals – Online Classes.

To read more about the previous article, please check the topic Hierarchical Datastructure – Binary Tree Implementation. To get updates on the other articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

This article will take over from where we wrapped up in the last article, It will define the remaining two methods elements() and positions() of the Tree ADT for LinkedBinaryTree. And we will also discuss the Tree traversals and code for the Binary Tree. We will finish up discussing all the three traversals using recursion approach as well.

The Inorder Tree Traversal

Before implementing the two remaining methods it is important to understand at least one of the tree traversal methods. We choose to learn the Inorder traversal first. As we discussed in the first article Hierarchical Datastructure – detailed discussion, the inorder traversal is one where we visit the left child of a node, then the node itself and at the end we visit the right child of the node.

How do we traverse in an inorder fashion?
Let us consider that we have total three nodes in the tree as below: The inorder traversal will print LC, R, RC.
tree3
Let us use another tree with few more nodes in the tree as below: The inorder traversal will print LC2, LC, RC2, R, LC3, RC, RC3
tree4

How does the algorithm work?

When we visit a node N, we check if it has a left child. In the event of finding a left child (C) we shift our focus to C and check if C has a left child, this process continue till we do not find a node (LC) in the left subtree without a left child. In event of finding such a node we print the value of the node LC and then we print the parent(PC) of LC. Now we shift our focus to the Right child of PC and repeat the same process till we reach the rightmost child of the right subtree of the root.

In case of the above diagram we stop traversing when we reach RC3 because it is the right most child of the right subtree. Now that we have some better understanding of the inorder traversal, we will write some code as well.

Explaining the recursion in the above method

This is a recursive approach, where we take the node which is passed as an argument, if it has left child then we invoke the same method with the left child of the node and repeat it till the node (let us say node X) in the current method invocation has a left child , after this we add the node X to the list of our nodes, and then we check if node X has a right child and continue this till we reach the top of the stack.

Lets consider the tree in the above picture, we pass the node R in the method with an empty list. We will discuss each invocation in detail and walk through the recursion. Let us say we have a list L which is empty in the beginning, also lets assume a recursion stack S which is empty in the beginning.

Invocation 1 : inOrderPositions(R, L) – evaluate the first if statement, R has a left child LC, so according to the recursive execution we push the node R in the recursion stack S. The state of list L is still empty but the stack S contains R.

Invocation 2 : inOrderPositions(LC, L) – evaluate the first if statement, LC has a left child LC2, so according to the recursive execution we push the node LC in the recursion stack S. The state of list L is still empty but the stack S contains R, LC.

Invocation 3 : inOrderPositions(LC2, L) – evaluate the first if statement, LC2 doesn’t have a left child, so we execute the next statement in the method and just add the node LC2 in the list. The list contains LC2. Now we evaluate the second if statement which lies in the sequence and find that the node LC2 doesn’t even have a right child, so we return from this invocation. Go back to Invocation 2 and pop up the element (that was pushed by Invocation 2 i.e. LC) at the top from the recursion stack S. The stack contains R.

We recall that in Invocation 2 we already have executed the first if condition, so now we execute the next statement in the sequence, where we add the present node (LC) into the list and the list contains LC2, LC. After adding LC to the list we need to execute the next statement in the sequence which is an if statement for the Invocation 2. We find that LC has a right child RC2, hence we invoke the method again with RCs as the parameter.

Invocation 4 : inOrderPositions(RC2, L) – evaluate the first if statement, RC2 doesn’t have a left child, so we execute the next statement in the method and just add the node RC2 in the list. The list contains LC2, LC, RC2. Now we evaluate the second if statement which lies in the sequence and find that the node RC2 doesn’t even have a right child, so we return from this invocation. Go back to Invocation 2.

When we return to Invocation 2 we learn that we already executed all the statements in the method for this particular invocation. So we return back to Invocation 1 and pop the top element from the stack (this was pushed by Invocation 1 i.e. R). If we see the Invocation 1, we get to know that the first if statement is already executed, so we execute the next statement in the sequence which adds the element R in the list. The list contains LC2, LC, RC2, R and the stack S is empty.

We execute the next statement in the method invocation which checks if the node R has a right child, and yes we find that it has a right child RC. So we start a new invocation passing RC into it.

Invocation 5 : inOrderPositions(RC, L) – evaluate the first if statement, RC has a left child LC3, so according to the recursive execution we push the node RC in the recursion stack S. Hence, S contains RC and we invoke the method with LC3 as a parameter.

Invocation 6 : inOrderPositions(LC3, L) – evaluate the first if statement, LC3 doesn’t have a left child, so we execute the next statement in the method and just add the node LC3 in the list. The list contains LC2, LC, RC2, R, LC3. Now we evaluate the second if statement which lies in the sequence and find that the node LC3 doesn’t even have a right child, so we return from this invocation. Go back to Invocation 5 and pop up the element (that was pushed by Invocation 5 i.e. RC) at the top from the recursion stack S. The stack becomes empty after this.

We recall that in Invocation 5 we already executed the first if, so now we will execute the next statement and add the node RC to the list. The list contains LC2, LC, RC2, R, LC3, RC. Then we evaluate the next if statement to find that RC has a right child RC3, we invoke the method with RC3 as a parameter.

Invocation 7 : inOrderPositions(RC3, L) – evaluate the first if statement, RC3 doesn’t have a left child, so we execute the next statement in the method and just add the node RC3 in the list. The list contains LC2, LC, RC2, R, LC3, RC, RC3. Now we evaluate the second if statement which lies in the sequence and find that the node RC3 doesn’t even have a right child, so we return from this invocation. Go back to Invocation 5.

Also, we have finished with all the statements of the method in Invocation 5. So we return back to Invocation 1 and find that all the statements in the method for Invocation 1 is also executed. So we are done with the traversal. The list now contains the result of the inorder traversal.

A tip to understand recursion : We always return from one invocation step I1 to another invocation step I2 if I1 was invoked immediately after I2.

All the traversals are done in a similar way and this understanding would help in understanding the rest of the traversals.

Implementing the Tree ADT methods

To implement the method positions() we can pass the root to this method and invoke the inOrderPositions method with the root and the empty list as arguments and when the inorderPositions method completes executions we get our list populated with the positions in an inorder fashion.

To implement the method elements() we can use a similar approach, we might need to change the inorderPositions method to return a list of elements and not positions.

The inOrderElements method:

Recursive Preorder Traversal

When we visit a node N, we add it to our list and check if it has a left child. In the event of finding a left child (C) we add C to the list and shift our focus to C and check if C has a left child, this process continue till we do not find a node (LC) in the left subtree without a left child. In event of finding such a node we add the node LC to our list and then we shift our focus to the right child of LC‘s parent(PC).We repeat the same process till we reach the rightmost child of the right subtree of the root.

Explanation with the above tree diagram

Step 1: Start at the root R and add R to the list and check if it has a left child.
Step 2: The left child is LC, add LC to the list and check if LC has a left child.
Step 3: The left child of LC is LC2, add LC2 to the list and check if LC2 has a left child.
Step 4: LC2 doesn’t have a left child, check if LC2 has a right child.
Step 5: LC2 doesn’t have a right child, so check if LC has a right child.
Step 6: The right child of LC is RC2, add RC2 to the list and check if RC2 has a left child.
Step 7: RC2 doesn’t have a left child, check if RC2 has a right child.
Step 8: RC2 doesn’t have a right child, so move up and check if R has a right child.
Step 9: The right child of R is RC, add RC to the list and check if RC has a left child.
Step10: The left child of RC is LC3, add LC3 to the list and check if RC3 has a left child.
Step11: RC3 doesn’t have a left child, check if RC3 has a right child.
Step12: RC3 doesn’t have a right child, so move up and check if RC has a right child.
Step13: RC has a right child RC3, add RC3 to the list and check if RC3 has a left child.
Step14: RC3 doesn’t have a left child, check if RC3 has a right child.
Step15: RC3 doesn’t have a right child, RC3 is the right most noe of the right subtree, so execution stops.

The final list would be R, LC, LC2, RC2, RC, LC3, RC3

The preorder traversal of the tree in the above diagram will result into R, LC, LC2, RC2, RC, LC3, RC3. The exaplanation is same as the one for inorder traversal.

Recursive Postorder Traversal

When we visit a node N, we check if it has a left child. In the event of finding a left child (C) we shift our focus to C and check if C has a left child, this process continue till we do not find a node (LC) in the left subtree without a left child. In event of finding such a node we add the node LC to the list and then we shift our focus to the right child of LC‘s parent(PC). Let us say that the right child is RC, then we repeat the same procedure of checking RC‘s left child and adding the node without a left child into the list ant then we add the right child and so on. The last node to be added in the list is the root.

Explanation with the above tree diagram

Step 1: Start at the root R and check if it has a left child.
Step 2: The left child is LC, check if LC has a left child.
Step 3: The left child of LC is LC2, check if LC2 has a left child.
Step 4: LC2 doesn’t have a left child, check if LC2 has a right child.
Step 5: LC2 doesn’t have a right child, so add LC2 in the list.
Step 6: Check the right child of LC, the right child of LC is RC2.
Step 7: Check if RC2 has a left child.
Step 8: RC2 doesn’t have a left child , check if RC2 has a right child.
Step 9: RC2 doesn’t have a right child, so add RC2 in the list.
Step10: Now add LC to the list and move up to the node R.
Step11: Check if R has a right child.
Step12: R has a right child RC, check if RC has a left child.
Step13: RC has a left child LC3, check if LC3 has a left child.
Step14: LC3 doesn’t have a left child, check if LC3 has a right child.
Step15: LC3 doesn’t have a right child, so add LC3 in the list.
Step16: Check the right child of RC, the right child of RC is RC3.
Step17: Check the left child of RC3, RC3 doesn’t have a left child.
Step18: Check the right child of RC3, RC3 doesn’t have a right child, so add RC3 in the list.
Step19: Now add RC to the list.
Step16: Move up and add R to the list.

The final list would be LC2, RC2, LC, LC3, RC3, RC, R

Conclusion

In this article we learnt the recursive approach of traversing the tree, and explained in detail each step used in this process. We learnt in details how recursion works and how the recursion stack works.

This gives us room to now move fast in the coming articles with all the algorithms for mirroring a tree, and traversing using iterative approach.

Hope this helps, happy reading. Stay connected and stay Subscribed