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