Binary Tree – Print all paths in a tree

Introduction

This is the seventh article in the series of non-linear data structures, to read more about the previous article, please check the topic Hierarchical Datastructure – Tree Traversals. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

This article is mostly about using our knowledge of tree to find out ways to solve real world problems and also perform some operations on the tree. We visit the problem to Print all paths in a tree.

Common Operations on a Tree

Here we assume that we already have a tree built in and we are just trying to perform one or the other operation which is listed down. We will be using the below tree for simplicity.
tree2

Printing all the paths in a Binary Tree

Here a path necessarily means the sequence of nodes visited from the root to a leaf, and here we are trying to print all the paths.

So by definition the paths in the above tree are as follows:

  1. ROOT – P1 – C1 – L1
  2. ROOT – P1 – C2 – L2
  3. ROOT – P3 – C4 – L5
  4. ROOT – P3 – C5

The task in hand is to understand the method or algorithm to print the same. We are going to use a recursive method to do the same. If you need a non-recursive one, please write down a comment and I will write another article for non-recursive operations on tree.

We will need an array where we can store all the paths and at the same time we need a counter for the path length because there will be various paths with different lengths. Here is the pseudo code and after that I will explain how it works. We will also do a dry run for our code.
paths_in_tree
The printPaths method is initially called with the root node , an empty array paths, and length as zero.

We return from the invocation of the method when the node passed is null.
If the node passed is not null, we add that node in the existing path, increase the path length by 1.

Then we evaluate if their is no left or right child, this is it, we print the path. In case we have either a left or a right child, we call the method recursively first with the left child and then with the right child.

This was a simple explanation which doesn’t make much sense, so let us do a dry run with our code and figure out the solution:

Invocation 1
At the beginning, the following are the state of the variables:
node = root
paths = []
length = 0

The node is not null, so add the node value i.e. ROOT to the array and increase the length by 1, length becomes 1 and paths become [ROOT].
The node has a left child P1 and a right child P3, so execute the first statement in else block which starts a new invocation i.e. Invocation 2 with the node argument as P1.

Invocation 2
At the beginning, the following are the state of the variables:
node = P1
paths = [ROOT]
length = 1

The node is not null, so add the node value i.e. P1 to the array and increase the length by 1, length becomes 2 and paths become [ROOT, P1].
The node has a left child C1 and a right child C2, so execute the first statement in else block which starts a new invocation i.e. Invocation 3 with the node argument as C1.

Invocation 3
At the beginning, the following are the state of the variables:
node = C1
paths = [ROOT, P1]
length = 2

The node is not null, so add the node value i.e. C1 to the array and increase the length by 1, length becomes 3 and paths become [ROOT, P1, C1].
The node has a left child L1 and no right child, so execute the first statement in else block which starts a new invocation i.e. Invocation 4 with the node argument as L1.

Invocation 4
At the beginning, the following are the state of the variables:
node = L1
paths = [ROOT, P1, C1]
length = 3

The node is not null, so add the node value i.e. L1 to the array and increase the length by 1, length becomes 4 and paths become [ROOT, P1, C1, L1].
The node has no left child or right child, so execute the if statement and print the paths array. Hence path printed is ROOT – P1 – C1 – L1

Now as I have discussed many times about recursion when there are no more statements left for execution in an invocation step of a method, then the execution shifts back to the parent invocation step. So we shift back to the Invocation 3, second statement in the else block.
Hence, Invocation 3 starts a new invocation i.e. Invocation 5 with the node argument as null because in Invocation 3 the node C1 didn’t have a right child.

Invocation 5
At the beginning, the following are the state of the variables:
node = null
paths = [ROOT, P1]
length = 2

The node is null, so return to the parent invocation i.e. Invocation 3 from where Invocation 5 is started.
Now Invocation 3 doesn’t have any statements left, so we move to the parent invocation of Invocation 3 and it is Invocation 2.
Execute the second statement in the else block of Invocation 2 and start a new invocation i.e. Invocation 6.

Invocation 6
At the beginning, the following are the state of the variables:
node = C2
paths = [ROOT, P1]
length = 2

The node is not null, so add the node value i.e. C2 to the array and increase the length by 1, length becomes 3 and paths become [ROOT, P1, C2].
The node has a left child L2 and no right child, so execute the first statement in else block which starts a new invocation i.e. Invocation 7 with the node argument as L2.

Invocation 7
At the beginning, the following are the state of the variables:
node = L2
paths = [ROOT, P1, C2]
length = 3

The node is not null, so add the node value i.e. L2 to the array and increase the length by 1, length becomes 4 and paths become [ROOT, P1, C2, L2].
The node has no left child or right child, so execute the if statement and print the paths array. Hence path printed is ROOT – P1 – C2 – L2

No statements left, so the execution shifts back to the parent invocation i.e. Invocation 6. Now execute the second statement in the else block which starts a new invocation i.e. Invocation 8 with node argument as null because there is no right child in the Invocation 6.

Invocation 8
At the beginning, the following are the state of the variables:
node = null
paths = [ROOT, P1]
length = 2

The node is null, so return to the parent invocation i.e. Invocation 6. All the statements in Invocation 6 is already executed, so move to parent invocation of Invocation 6 i.e. Invocation 2. All the statements of Invocation 2 are already over, so move to it’s parent invocation i.e. Invocation 1. Now execute the second statement in the else block of Invocation 1. It starts a new Invocation i.e. Invocation 9 with node argument P3.

Invocation 9
At the beginning, the following are the state of the variables:
node = P3
paths = [ROOT]
length = 1

The node is not null, so add the node value i.e. P3 to the array and increase the length by 1, length becomes 2 and paths become [ROOT, P3].
The node has a left child C4 and a right child C5, so execute the first statement in else block which starts a new invocation i.e. Invocation 10 with the node argument as C4.

Invocation 10
At the beginning, the following are the state of the variables:
node = C4
paths = [ROOT, P3]
length = 2

The node is not null, so add the node value i.e. C4 to the array and increase the length by 1, length becomes 3 and paths become [ROOT, P3, C4].
The node has no left child but it has a right child L5, so execute the first statement in else block which starts a new invocation i.e. Invocation 11 with the node argument as null.

Invocation 11
At the beginning, the following are the state of the variables:
node = null
paths = [ROOT, P3, C4]
length = 3

The node is null,so return to the parent invocation i.e. Invocation 10. Execute the second statement in the else block, which starts a new invocation i.e. Invocation 12 with the node argument L5.

Invocation 12
At the beginning, the following are the state of the variables:
node = L5
paths = [ROOT, P3, C4]
length = 3

The node is not null, so add the node value i.e. L5 to the array and increase the length by 1, length becomes 4 and paths become [ROOT, P3, C4, L5].
The node has no left child or right child, so execute the if statement and print the paths array. Hence path printed is ROOT – P3 – C4 – L5

No statements left, so the execution shifts back to the parent invocation i.e. Invocation 10. There is no statements left in the Invocation 10 as well, so execution shifts to the parent invocation of Invocation 10 i.e. Invocation 9. Execute the second statement in the else block of Invocation 9, it starts a new invocation i.e. Invocation 13 with the node argument C5.

Invocation 13
At the beginning, the following are the state of the variables:
node = C5
paths = [ROOT, P3]
length = 2

The node is not null, so add the node value i.e. C5 to the array and increase the length by 1, length becomes 3 and paths become [ROOT, P3, C5].
The node has no left child or right child, so execute the if statement and print the paths array. Hence path printed is ROOT – P3 – C5

No statements left, so the execution shifts back to the parent invocation i.e. Invocation 9. There is no statements left in the Invocation 9 as well, so execution shifts to the parent invocation of Invocation 9 i.e. Invocation 1. There is no statements to be executed in Invocation 1 as well. Hence the execution stops and we have printed the four paths.

Source Code

Here is the complete source code for all the tree related stuff we have written till now.
Source Code

Analysis

There is nothing much to analyze here, the running time is O(n) because we visit each node just once, and that is the best we can do, to print all the paths we have to see each node at least once. There can be worst performances though, where we start from the root every time and keep a track on which all nodes we have already printed.

The space complexity is O(length of the longest path). As we require to store one path at a time, and we will need space equivalent to the longest path, hence it takes that much of space.

Conclusion

In this article we learnt the recursive way of printing all the paths in a binary tree.

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