Left Hand Projection of a Tree

Introduction

Another interesting interview question, this question has many forms. One of the form is print the left hand projection of a tree or right hand projection of a tree or so on. Also, this problem can be specialized for a binary tree, ternary tree or n-ary tree, it really doesn’t matter, the concept is the same.

We will just try and print the left hand projection and I will add a note on how to print the right had project and you can try that yourself.

Understanding the problem – Left Hand Projection of a Tree

Let us consider the below tree for our problem statement.
Left Hand Projection of a Tree

What is Left Hand Projection of a Tree?

The left hand projection means the nodes which we can see if we look at the tree from the left hand side. This translates to the following:

  • We have to pick up one node at each level.
  • The node is the first one on that level.
  • The number of nodes in the left hand projection would be equal to the height of the tree (because we take one node per level).

For the above tree the left hand projection would be : 1, 2, 6, 13, 15, 18

What is Right Hand Projection of a Tree?

The right hand projection means the nodes which we can see if we look at the tree from the right hand side. This translates to the following:

  • We have to pick up one node at each level.
  • The node is the last one on that level.
  • The number of nodes in the right hand projection would be equal to the height of the tree (because we take one node per level).

For the above tree the right hand projection would be : 1, 5, 12, 14, 17, 19

Note: If the tree has one node per level then the left hand projection is exactly same as the right hand projection.

Solution

The idea for the solution is similar to the one for Level Order Traversal. It’s just that at each level we are only interested in the first or the last node.

Pseudo Code

Similarly you can write the pseudo code for the right hand projection.

Source Code – Left Hand Projection of a Tree

Here is the source code for the n-ary tree, if you want to do it for a binary tree, you can replace the node.getChildren with node.getRight and node.getLeft.

Please download the complete source code from the Techieme Github repository.

Complexity Analysis

Running Time : The outer loop seems to run for N times where N is the total number of nodes. But the case is slightly different, the outer loop just runs for H times where H is the number of levels or height of the tree.
The inner loop runs for K times per level where K is the number of nodes in the particular level. This means the total running time of the algorithm is O(N) where N is the number of nodes.

Space Complexity : No extra space is being used, hence the space complexity is constant O(1).

Conslusion

This problem is same a level order tree traversal. Similar problems can be also created for top projection and bottom projection. They may evolve to be a complex one. We will discuss them in some other post.

Don’t forget to subscribe to TechieMe to get updates on latest posts.