DAA: Algorithm of Right View of a Binary Tree
Algorithm of Right View of a Binary Tree
The right view of a binary tree is the visible nodes from the right side of the tree.
In the given tree, the visible nodes from the right side are one, three, and six. Hence the right view is 1 3 6.
In other words, we can say that the right view of a binary tree contains the last nodes at each level.
How can we approach this problem?
Approach 1
Recursion can be a great help to solve this problem. Keep track of each level and maximum level. Now we will traverse in a way such that the right subtree is traversed before the left subtree. Whenever we strike a node whose level is more than the maximum level so far, we print the last node in its level.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Create tree Structure
struct Node {
int data; // Value of the tree Node
struct Node *left, *right; // Left and right pointer to the node
};
// Allocate memory to the newely created node
struct Node* newNode(int item)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); // Allocate //memory
temp->data = item; // Insert the data
temp->left = temp->right = NULL; // The right and left of current child is NULL
return temp; // return currrent node
}
// The function will print the right view nodes of binary tree
void right_View_Util(struct Node* root, int level, int* max_level)
{
//If we reach the last level
if (root == NULL)
return;
//If currrent max is less than level
if (*max_level < level) {
cout << root->data << "\t"; // print last node
*max_level = level; // Make it as currrent max.
}
// Recurisvley call for the left and right subtrees
right_View_Util(root->right, level + 1, max_level);
right_View_Util(root->left, level + 1, max_level);
}
// Helper for Right View funtion
void right_View(struct Node* root)
{
int max_level = 0; // initlaise max level as 0
right_View_Util(root, 1, &max_level);
}
int main() // Main function
{
struct Node* root = newNode(1); //create root node
root->left = newNode(2); // create left node
root->right = newNode(3); // create right node
root->left->left = newNode(4); // left child of left node
root->left->right = newNode(5); // right child of left node
root->right->left = newNode(6); // left child of right parent node
root->right->right = newNode(7); // right child of right parent node
root->right->left->right = newNode(8);
right_View(root);
return 0;
}
C Code:
#include <stdio.h>
#include <stdlib.h>
// Create tree Structure
struct Node {
int data; // Value of the tree Node
struct Node *left, *right; // Left and right pointer to the node
};
// Allocate memory to the newely created node
struct Node* newNode(int item)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
temp->data = item; // Insert the data
temp->left = temp->right = NULL; // The right and left of current child is NULL
return temp; // return currrent node
}
// The function will print the right view nodes of binary tree
void right_View_Util(struct Node* root, int level, int* max_level)
{
//If we reach the last level
if (root == NULL)
return;
//If currrent max is less than level
if (*max_level < level) {
printf("%d\t", root->data); // print last node
*max_level = level; // Make it as currrent max.
}
// Recurisvley call for the left and right subtrees
right_View_Util(root->right, level + 1, max_level);
right_View_Util(root->left, level + 1, max_level);
}
// Helper for Right View funtion
void right_View(struct Node* root)
{
int max_level = 0; // initlaise max level as 0
right_View_Util(root, 1, &max_level);
}
int main() // Main function
{
struct Node* root = newNode(1); //create root node
root->left = newNode(2); // create left node
root->right = newNode(3); // create right node
root->left->left = newNode(4); // left child of left node
root->left->right = newNode(5); // right child of left node
root->right->left = newNode(6); // left child of right parent node
root->right->right = newNode(7); // right child of right parent node
root->right->left->right = newNode(8);
right_View(root);
return 0;
}
Output:
1 3 7 8
Approach 2
This approach will use a queue data structure, do level order traversal, and print the tree’s rightmost node.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Create tree Structure
struct Node {
int data; // Value of the tree Node
struct Node *left, *right; // Left and right pointer to the node
};
// Allocate memory to the newly created node
struct Node* newNode(int item)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); // Allocate //memory
temp->data = item; // Insert the data
temp->left = temp->right = NULL; // The right and left of current child is NULL
return temp; // return currrent node pointer
}
void right_View(Node* root) // This will print the right view of the binary tree
{
if (!root) // If tree is empty we return
return;
// Delcare a queue of Node Structure
queue<Node*> q;
q.push(root); // Push the root in the queue
while (!q.empty()) // Iterate in the queue
{
int n = q.size(); // here n is number of node at current level
// Loop through all the nodes in the level
for (int i = 1; i <= n; i++) {
Node* temp = q.front(); // Take front node from the queue
q.pop(); // pop the front node from the queue
if (i == n) // if we reach the last node print the data of last node
cout << temp->data << "\t";
// If the left node exist push in queue
if (temp->left != NULL)
q.push(temp->left);
// If the right node of the current level exist push in queue
if (temp->right != NULL)
q.push(temp->right);
}
} // Run the loop until all level is traversed
}
int main() // Main function
{
struct Node* root = newNode(1); //create root node
root->left = newNode(2); // create left node
root->right = newNode(3); // create right node
root->left->left = newNode(4); // left child of left node
root->left->right = newNode(5); // right child of left node
root->right->left = newNode(6); // left child of right parent node
root->right->right = newNode(7); // right child of right parent node
root->right->left->right = newNode(8);
right_View(root);
return 0;
}
Output:
1 3 7 8
Time complexity: O(n) where n is the nodes in the binary tree
Space complexity: O(n), where n is the number of nodes in the binary tree