Print different views of Tree like a Top, Bottom, Left, Right?

Question: Print different views of Tree like a Top, Bottom, Left, Right?

Problem link: https://www.hackerrank.com/challenges/tree-top-view/problem

Answer 

I am using Recursive approach to solve this Question, As it is easier to understand and explain, but it can lend up in stack overflow problem in case of a huge tree. It is good if we have some idea about the iterative approach. Followup Question may be asked that is the internal working of TreeMap and its data structure and its time complexity of inserting the data and traversing it.

1. TopView

 

To solve this Question, First, start thinking about how we can traverse the tree.

We can use recursion with the base condition that starts traversing left part of the tree and then right part. Here we got the hit that if we maintain horizontal distance from the root node that can give us the Top/Bottom view tree. 

To get the particular tree we use the level to get the specific Top/Bottom view tree.

Pair is a class that holds the two number that is node value and its level.

Time Complexity: O(n)

Space Complexity: O(n)

2. Bottom View

Only this below condition is changed.In order to get the bottom view of tree.

!map.containsKey(dist) || level >= map.get(dist).level

Time Complexity: O(n)

Space Complexity: O(n)

3. Left View 

now, this becomes easier as here we just need to maintain the max level till now while doing pre-order traversal.

Time Complexity: O(n)

Space Complexity: O(1)

4.Right View

now, this becomes easier as here we just need to maintain the max level till now while doing post-order traversal.

Time Complexity: O(n)

Space Complexity: O(1)

Code Solution :

Console 

6

1 2 5 3 6 4

Tree:  

  1

    \

     2

      \

       5

      /  \

     3    6

      \

       4

Top View: 

1 2 5 6 

Bottom View: 

1 3 4 6 

Left View: 

1 2 5 3 4 

Right View: 

1 2 5 6 4 

Recursion In Maze Game

Question: Print all possible path in the 2D array from source to destination. Allowed motion is Horizontal right and vertical down.

Vinsol : Defected Meter

Question :A Defected meter is given with missing number 4 from it's rim.WAP that convert the wrong  reading into right one.

Example:

input 100

output 81

JOSH:Question: WAP that sum up all one child parent nodes without globle variable

//Question: WAP that sum up all one child parent nodes without globle variable
//             3
//            / \
//          4    5
//         / \   \
//        6   8    9
//            /
//           7
//output 8+5=13

JOSH: WAP that sum up all leaf nodes without globle variable

Question: 

WAP that sum up all leaf nodes without globle
input tree  3
           / \
         4    5
        / \    \
       6   8    9
          /
         7
Output 6+7+9=22