Tree : Top View Hackerrank problem solution

Tree : Top View Hackerrank

You are given a pointer to the root of a binary tree. Print the top view of the binary tree.
You only have to complete the function.
For example :

3
/ \
5 2
/ \ / \
1 4 6 7
\ /
9 8

Top View : 1 -> 5 -> 3 -> 2 -> 7
Input Format

You are given a function,

void top_view(node * root)
{

}

Output Format

Print the values on a single line separated by space.

Sample Input

3
/ \
5 2
/ \ / \
1 4 6 7
\ /
9 8

Sample Output

1 5 3 2 7
Explanation

3
/ \
5 2
/ \ / \
1 4 6 7
\ /
9 8

From the top only nodes 1,5,3,2 and 7 will be visible.

Solution

The basic algorithm is as follows:
Write a method that goes left. Go left until you can’t go left anymore, and print each value in such a way that the leftmost nodes in the left subtree will print from left to right. We do this by recursively calling our goLeft method on the next valid left subtree and then printing the value for the current node. This ordering ensures that the leftmost element is at the top of the call stack and will be printed first once we reach the leftmost subtree (and then each parent will be printed as the calling methods are popped off the call stack).
Print the root’s value.
Write a method that goes right. This is similar to the goLeft logic, with a minor change. We want to print each rightmost node’s value as we go right, so we just print the current node’s value and then recursively call the goRight method on the current node’s right subtree.
Note: This solution is overly simplified and you will need something more complicated for certain types of imbalanced trees.

/*
struct node
{
    int data;
    node* left;
    node* right;
};

*/

int top=-1,arr[100];

void push(int x)
{
    top++;
    arr[top]=x;
}

void top_view(node * root)
{
struct node *temp=root->right;   
    while(root!=NULL)
{
    push(root->data);
    root=root->left;

}
while(top!=-1)
{
   cout<<arr[top]<<" ";
   top--;
}

    while(temp!=NULL)
    {
    cout<<temp->data<<" ";
    temp=temp->right;
}

}
/*
struct node
{
    int data;
    node* left;
    node* right;
};

*/

void left_side(node* root)
{
    if (root == NULL) return;

     left_side(root->left);
     cout<<root->data<<" ";
}

void right_side (node* root)
 {
    if (root == NULL) return;
    cout<<root->data<<" ";
    right_side(root->right);

}

void top_view(node * root)
{
   if(root != NULL)
    {
   left_side( root->left);
   cout<<root->data<<" ";
   right_side( root->right);
   }

}
void goLeft(Node node) {
    if(node.left != null) {
        goLeft(node.left);
    }
    System.out.print(node.data + " ");
}

void goRight(Node node) {
    System.out.print(node.data + " ");
    
    if(node.right != null) {
        goRight(node.right);
    }
}

void top_view(Node root) {
    if(root.left != null) {
        goLeft(root.left);
    }
    
    System.out.print(root.data + " ");
    
    if(root.right != null) {
        goRight(root.right);
    }
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

2 comments: On Tree : Top View Hackerrank problem solution

Leave a reply:

Your email address will not be published.