In C language, print the right view of the binary tree

The task is to print the right node of the given binary tree. First the user will insert data to create a binary tree and then print a right view of the resulting tree.

The above image shows a binary tree created using nodes 10, 42, 93, 14, 35, 96, 57 and 88, with the ones selected and displayed on the right side of the tree node. For example, 10, 93, 57, and 88 are the rightmost nodes of the binary tree.

Example

Input : 10 42 93 14 35 96 57 88
Output : 10 93 57 88

Each node has two pointers, a left pointer and a right pointer. According to this question, the program only needs to traverse the right node. Therefore, the left child of the node does not need to be considered.

The right view stores all nodes that are the last node of their level. Therefore, we can simply use recursive methods to store and access nodes in such a way that the right subtree is traversed first and then the left subtree. Whenever the program detects that the level of a node is greater than the level of the previous node, the previous node is displayed because it will be the last node in its level.

The following code shows the C language implementation of a given algorithm

Algorithm

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *left, *right
   Step 2 -> create function for inserting node with parameter as item
      Declare temp variable of node using malloc
      Set temp->data = item
      Set temp->left = temp->right = NULL
      return temp
   step 3 -> Declare Function void right_view(struct node *root, int level, int *end_level)
      IF root = NULL
         Return
      IF *end_level < level
         Print root->data
         Set *end_level = level
         Call right_view(root->right, level+1, end_level)
         Call right_view(root->left, level+1, end_level)
   Step 4 -> Declare Function void right(struct node *root)
      Set int level = 0
      Call right_view(root, 1, &level)
   Step 5 -> In Main()
      Pass the values for the tree nodes using struct node *root = New(10)
      Call right(root)
STOP

The Chinese translation of

is:

Example

#include<stdio.h>
#include<stdlib.h>
struct node {
   int data;
   struct node *left, *right;
};
struct node *New(int item) {
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->left = temp->right = NULL;
   return temp;
}
void right_view(struct node *root, int level, int *end_level) {
   if (root == NULL) return;
   if (*end_level < level) {
      printf("%d\t", root->data);
      *end_level = level;
   }
   right_view(root->right, level+1, end_level);
   right_view(root->left, level+1, end_level);
}
void right(struct node *root) {
   int level = 0;
   right_view(root, 1, &level);
}
int main() {
   printf("right view of a binary tree is : ");
   struct node *root = New(10);
   root->left = New(42);
   root->right = New(93);
   root->left->left = New(14);
   root->left->right = New(35);
   root->right->left = New(96);
   root->right->right = New(57);
   root->right->left->right = New(88);
   right(root);
   return 0;
}

Output

If we run the above program, it will generate the following output.

right view of a binary tree is : 10 93 57 88

The above is the detailed content of In C language, print the right view of the binary tree. For more information, please follow other related articles on the PHP Chinese website!