Given a binary tree, the task is to find the sum of the nodes which are visible in the right view. The right view of a binary tree is the set of nodes visible when the tree is viewed from the right.
Examples:
Input:
1
/ \
2 3
/ \ \
4 5 6
Output: 10
1 + 3 + 6 = 10
Input:
1
/ \
2 3
\
4
\
5
\
6
Output: 19
Approach: The problem can be solved using simple recursive traversal. We can keep track of the level of a node by passing a parameter to all the recursive calls. The idea is to keep track of the maximum level also and traverse the tree in a manner that the right subtree is visited before the left subtree. Whenever a node whose level is more than the maximum level so far is encountered, add the value of the node to the sum because it is the last node in its level (Note that the right subtree is traversed before the left subtree).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node *left, *right;};// A utility function to create// a new Binary Tree NodeNode* newNode(int item){ Node* temp = new Node(); temp->data = item; temp->left = temp->right = NULL; return temp;}// Recursive function to find the sum of nodes// of the right view of the given binary treevoid sumRightViewUtil(Node* root, int level, int* max_level, int* sum){ // Base Case if (root == NULL) return; // If this is the last Node of its level if (*max_level < level) { *sum += root->data; *max_level = level; } // Recur for left and right subtrees sumRightViewUtil(root->right, level + 1, max_level, sum); sumRightViewUtil(root->left, level + 1, max_level, sum);}// A wrapper over sumRightViewUtil()void sumRightView(Node* root){ int max_level = 0; int sum = 0; sumRightViewUtil(root, 1, &max_level, &sum); cout << sum;}// Driver codeint main(){ Node* root = newNode(12); root->left = newNode(10); root->right = newNode(30); root->right->left = newNode(25); root->right->right = newNode(40); sumRightView(root); return 0;} |
Java
// Java implementation of the approach// Class for a node of the treeclass Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; }}class BinaryTree { Node root; static int max_level = 0; static int sum = 0; // Recursive function to find the sum of nodes // of the right view of the given binary tree void sumRightViewUtil(Node node, int level) { // Base Case if (node == null) return; // If this is the last node of its level if (max_level < level) { sum += node.data; max_level = level; } // Recur for left and right subtrees sumRightViewUtil(node.right, level + 1); sumRightViewUtil(node.left, level + 1); } // A wrapper over sumRightViewUtil() void sumRightView() { sumRightViewUtil(root, 1); System.out.print(sum); } // Driver code public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(12); tree.root.left = new Node(10); tree.root.right = new Node(30); tree.root.right.left = new Node(25); tree.root.right.right = new Node(40); tree.sumRightView(); }} |
Python3
# Python3 implementation of the approach# A binary tree node class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None# Recursive function to find the sum of nodes # of the right view of the given binary treedef sumRightViewUtil(root, level, max_level, sum): # Base Case if root is None: return # If this is the last node of its level if (max_level[0] < level): sum[0]+= root.data max_level[0] = level # Recur for left and right subtree sumRightViewUtil(root.right, level + 1, max_level, sum) sumRightViewUtil(root.left, level + 1, max_level, sum) # A wrapper over sumRightViewUtil() def sumRightView(root): max_level = [0] sum =[0] sumRightViewUtil(root, 1, max_level, sum) print(sum[0])# Driver coderoot = Node(12) root.left = Node(10) root.right = Node(30) root.right.left = Node(25) root.right.right = Node(40) sumRightView(root) |
C#
// C# implementation of the approachusing System;// Class for a node of the treepublic class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}public class BinaryTree { public Node root; public static int max_level = 0; public static int sum = 0; // Recursive function to find the sum of nodes // of the right view of the given binary tree public virtual void sumrightViewUtil(Node node, int level) { // Base Case if (node == null) { return; } // If this is the last node of its level if (max_level < level) { sum += node.data; max_level = level; } // Recur for left and right subtrees sumrightViewUtil(node.right, level + 1); sumrightViewUtil(node.left, level + 1); } // A wrapper over sumrightViewUtil() public virtual void sumrightView() { sumrightViewUtil(root, 1); Console.Write(sum); } // Driver code public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(12); tree.root.left = new Node(10); tree.root.right = new Node(30); tree.root.right.left = new Node(25); tree.root.right.right = new Node(40); tree.sumrightView(); }} |
Javascript
<script> // JavaScript implementation of the approach // Class for a node of the tree class Node { constructor(item) { this.left = null; this.right = null; this.data = item; } } let root; let max_level = 0; let sum = 0; // Recursive function to find the sum of nodes // of the right view of the given binary tree function sumRightViewUtil(node, level) { // Base Case if (node == null) return; // If this is the last node of its level if (max_level < level) { sum += node.data; max_level = level; } // Recur for left and right subtrees sumRightViewUtil(node.right, level + 1); sumRightViewUtil(node.left, level + 1); } // A wrapper over sumRightViewUtil() function sumRightView() { sumRightViewUtil(root, 1); document.write(sum); } root = new Node(12); root.left = new Node(10); root.right = new Node(30); root.right.left = new Node(25); root.right.right = new Node(40); sumRightView();</script> |
Output
82
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(n), where n is the number of nodes in the binary tree.
Iterative Approach(Using Queue):
Follow the below steps to solve the above problem:
1) Simply traverse the whole binary tree in level Order Traversal with the help of Queue data structure.
2) At each level keep track of the sum and add last node data in sum.
3) Finally print the sum.
Below is the implementation of the above approach:
C++
// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999)// C++ Program for the above approach#include<bits/stdc++.h>using namespace std;struct Node{ int data; Node* left; Node* right; Node(int data){ this->data = data; this->left = this->right = NULL; }};// A utility function to create a new nodestruct Node* newNode(int data){ return new Node(data);}void sumRightView(Node* root){ if(root == NULL) return; queue<Node*> q; q.push(root); int sum = 0; while(!q.empty()){ int n = q.size(); for(int i = 0; i<n; i++){ Node* front_node = q.front(); q.pop(); if(i == n-1) sum = sum + front_node->data; if(front_node->left) q.push(front_node->left); if(front_node->right) q.push(front_node->right); } } cout<<sum<<endl;}// driver program to test above functionint main(){ Node* root = newNode(12); root->left = newNode(10); root->right = newNode(30); root->right->left = newNode(25); root->right->right = newNode(40); sumRightView(root); return 0;} |
Java
// Java Program for the above approachimport java.util.*;class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; }}public class Main { static void sumRightView(Node root) { if (root == null) return; Queue<Node> q = new LinkedList<>(); q.offer(root); int sum = 0; while (!q.isEmpty()) { int n = q.size(); for (int i = 0; i < n; i++) { Node front_node = q.poll(); if (i == n - 1) sum = sum + front_node.data; if (front_node.left != null) q.offer(front_node.left); if (front_node.right != null) q.offer(front_node.right); } } System.out.println(sum); } // driver program to test above function public static void main(String[] args) { Node root = new Node(12); root.left = new Node(10); root.right = new Node(30); root.right.left = new Node(25); root.right.right = new Node(40); sumRightView(root); }}// This code is contributed by Saroj Mandal |
Python3
# Python3 Program for the above approachfrom queue import Queueclass Node: def __init__(self, data): self.data = data self.left = None self.right = Nonedef sumRightView(root): if root is None: return q = Queue() q.put(root) sum = 0 while not q.empty(): n = q.qsize() for i in range(n): front_node = q.get() if i == n-1: sum += front_node.data if front_node.left: q.put(front_node.left) if front_node.right: q.put(front_node.right) print(sum)# driver program to test above functionif __name__ == '__main__': root = Node(12) root.left = Node(10) root.right = Node(30) root.right.left = Node(25) root.right.right = Node(40) sumRightView(root) |
Javascript
// JavaScript Program for the above approachclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}function sumRightView(root) { if (!root) return; const q = []; q.push(root); let sum = 0; while (q.length !== 0) { const n = q.length; for (let i = 0; i < n; i++) { const front_node = q.shift(); if (i === n - 1) sum = sum + front_node.data; if (front_node.left) q.push(front_node.left); if (front_node.right) q.push(front_node.right); } } console.log(sum);}// driver program to test above functionconst root = new Node(12);root.left = new Node(10);root.right = new Node(30);root.right.left = new Node(25);root.right.right = new Node(40);sumRightView(root); |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;public class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; this.left = this.right = null; }}public class MainClass { static void sumRightView(Node root) { if (root == null) return; Queue < Node > q = new Queue < Node > (); q.Enqueue(root); int sum = 0; while (q.Count != 0) { int n = q.Count; for (int i = 0; i < n; i++) { Node front_node = q.Dequeue(); if (i == n - 1) sum = sum + front_node.data; if (front_node.left != null) q.Enqueue(front_node.left); if (front_node.right != null) q.Enqueue(front_node.right); } } Console.WriteLine(sum); } // driver program to test above function public static void Main() { Node root = new Node(12); root.left = new Node(10); root.right = new Node(30); root.right.left = new Node(25); root.right.right = new Node(40); sumRightView(root); }}// Contributed by adityasharmadev01 |
Output
82
Time Complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(N) due to queue data structure.
Another Approach(Using Morris Traversal):
Follow the below steps to solve the above problem:
1) Initialize a sum variable to hold the result.
2) Initialize a pointer curr to the root of the binary tree.
3) While curr is not null, do the following:
If curr has no right child: Add the value of curr to sum and set curr to its right child.
Otherwise: Find inorder successor of curr by initializing a pointer next to right child of curr, and then repeatedly moving left until next has no left child or its left child is equal to curr.
4) If next has no left child: Add the value of curr to sum, set the left child of next to curr, set curr to its right child.
Otherwise: Set the left child of next to null, set curr to its left child. Return sum, which contains the sum of nodes in right view of binary tree.
Below is the implementation of above approach:
C++
// C++ program to find the sum of nodes// in right view of binary tree #include <bits/stdc++.h>using namespace std;// Structure of the binary tree nodestruct Node{ int data; Node* left; Node* right;}; // Utility function to create a new NodeNode* newNode(int item){ Node* temp = new Node(); temp->data = item; temp->left = temp->right = NULL; return temp;}int sumRightView(Node* root){ int sum = 0; Node* curr = root; while (curr) { // if there is not right child add current node's value to vector if (!curr->right) { sum += curr->data; // move to the right child curr = curr->right; } // If there is a right child else { // set the next node to the right child Node* next = curr->right; // traverse the left subtree of the right child until a // leaf node or the current node is reached while (next->left && next->left != curr) next = next->left; // if the left child of the next node is NULL if (!next->left) { sum += curr->data; next->left = curr; curr = curr->right; } else { next->left = NULL; curr = curr->left; } } } return sum;}// Driver codeint main(){ Node* root = newNode(12); root->left = newNode(10); root->right = newNode(30); root->right->left = newNode(25); root->right->right = newNode(40); cout<<sumRightView(root); return 0;}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
82
Time Complexity: O(n), where n is the number of nodes in given binary tree.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
