How to get the Right View of a Binary Tree?

Question

Given Tree

          6
       /     \
     7        8
   /   \     /  \
  9    10  11    12
                  \
                   13

Expected Output
6 8 12 13

Answer 1

A simple solution is to do level order traversal and print the last node in every level. Following is the program to get the right side view of the binary tree

struct Node
{
    int data;
    struct Node *left, *right;
};

struct Node *newNode(int item)
{
    struct Node *temp =  (struct Node *)malloc(sizeof(struct Node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Recursive function to print right view of a binary tree.
void rightViewUtil(struct Node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;

    // If this is the first Node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }

    // Recur for right subtree first, then left subtree
    rightViewUtil(root->right, level+1, max_level);
    rightViewUtil(root->left, level+1, max_level);
}


void rightView(struct Node *root)
{
    int max_level = 0;
    rightViewUtil(root, 1, &max_level);
}

int main()
{
    struct Node *root = newNode(6);
    root->left = newNode(7);
    root->right = newNode(8);
    root->left->left = newNode(9);
    root->left->right = newNode(10);
    root->right->left = newNode(11);
    root->right->right = newNode(12);
    root->right->left->right = newNode(13);

    rightView(root);

    return 0;
}

Output

6   8   12  13