Given a Binary Tree, print Bottom-Right view of it. The Bottom Right view of a Binary Tree is a set of nodes visible when the tree is visited from Bottom Right side, return the values of the nodes ordered from right to left.
In the bottom-right view, on viewing the tree at an angle of 45 degrees from the bottom-right side and only a few nodes would be visible and rest would be hidden behind them.
Examples:
Input :
1
/ \
2 3
\ \
5 4
Output : [4, 5]
Visible nodes from the bottom right direction are 4 and 5
Input :
1
/ \
2 3
/ /
4 5
\
6
Output: [3, 6, 4]
Approach :
- The problem can be solved using simple recursive traversal.
- Keep track of the level of a node by passing a parameter to all recursive calls. Consider the level of a tree at an angle of 45% (as explained in an example), so whenever we move towards the left, its level would increase by one.
- The idea is to keep track of the maximum level and traverse the tree in a manner that right subtree is visited before left subtree.
- A node whose level is more than maximum level so far, Print the node because this is the last node in its level (Traverse the right subtree before left subtree).
Below is the implementation of the above approach:
C++
// C++ program to print bottom// right view of binary tree#include<bits/stdc++.h>using namespace std;// A binary tree nodestruct Node{ int data; Node *left, *right; Node(int item) { data = item; left = right = NULL; }};// class to access maximum level // by referencestruct _Max_level { int _max_level;};Node *root;_Max_level *_max = new _Max_level();// Recursive function to print bottom// right view of a binary treevoid bottomRightViewUtil(Node* node, int level, _Max_level *_max_level){ // Base Case if (node == NULL) return; // Recur for right subtree first bottomRightViewUtil(node->right, level, _max_level); // If this is the last Node of its level if (_max_level->_max_level < level) { cout << node->data << " "; _max_level->_max_level = level; } // Recur for left subtree // with increased level bottomRightViewUtil(node->left, level + 1, _max_level);}// A wrapper over bottomRightViewUtil()void bottomRightView(Node *node){ bottomRightViewUtil(node, 1, _max);}void bottomRightView(){ bottomRightView(root);}// Driver Codeint main(){ root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->left->right = new Node(6); bottomRightView();}// This code is contributed by Arnab Kundu |
Java
// Java program to print bottom// right view of binary tree// A binary tree nodeclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}// class to access maximum level by referenceclass Max_level { int max_level;}class BinaryTree { Node root; Max_level max = new Max_level(); // Recursive function to print bottom // right view of a binary tree. void bottomRightViewUtil(Node node, int level, Max_level max_level) { // Base Case if (node == null) return; // Recur for right subtree first bottomRightViewUtil(node.right, level, max_level); // If this is the last Node of its level if (max_level.max_level < level) { System.out.print(node.data + " "); max_level.max_level = level; } // Recur for left subtree with increased level bottomRightViewUtil(node.left, level + 1, max_level); } void bottomRightView() { bottomRightView(root); } // A wrapper over bottomRightViewUtil() void bottomRightView(Node node) { bottomRightViewUtil(node, 1, max); } // Driver program to test the above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.right.left = new Node(5); tree.root.right.left.right = new Node(6); tree.bottomRightView(); }} |
Python3
# Python3 program to print bottom# right view of binary tree# A binary tree nodeclass Node: # Construct to create a newNode def __init__(self, item): self.data = item self.left = None self.right = Nonemaxlevel = [0]# Recursive function to print bottom# right view of a binary tree.def bottomRightViewUtil(node, level, maxlevel): # Base Case if (node == None): return # Recur for right subtree first bottomRightViewUtil(node.right, level, maxlevel) # If this is the last Node of its level if (maxlevel[0] < level): print(node.data, end = " ") maxlevel[0] = level # Recur for left subtree with increased level bottomRightViewUtil(node.left, level + 1, maxlevel)# A wrapper over bottomRightViewUtil()def bottomRightView(node): bottomRightViewUtil(node, 1, maxlevel) # Driver Coderoot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.right.left = Node(5)root.right.left.right = Node(6)bottomRightView(root)# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to print bottom// right view of binary treeusing System;// A binary tree nodeclass Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}// class to access maximum level by referenceclass Max_level{ public int max_level;}class GFG { Node root; Max_level max = new Max_level(); // Recursive function to print bottom // right view of a binary tree. void bottomRightViewUtil(Node node, int level, Max_level max_level) { // Base Case if (node == null) return; // Recur for right subtree first bottomRightViewUtil(node.right, level, max_level); // If this is the last Node of its level if (max_level.max_level < level) { Console.Write(node.data + " "); max_level.max_level = level; } // Recur for left subtree with increased level bottomRightViewUtil(node.left, level + 1, max_level); } void bottomRightView() { bottomRightView(root); } // A wrapper over bottomRightViewUtil() void bottomRightView(Node node) { bottomRightViewUtil(node, 1, max); } // Driver Code public static void Main(String []args) { GFG tree = new GFG(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.right.left = new Node(5); tree.root.right.left.right = new Node(6); tree.bottomRightView(); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to print bottom// right view of binary tree// A binary tree nodeclass Node { constructor(item) { this.data = item; this.left = null; this.right = null; }}// class to access maximum level by referenceclass Max_level{ constructor() { this.max_level = 0; }}var max = new Max_level();// Recursive function to print bottom// right view of a binary tree.function bottomRightViewUtil(node, level,max_level){ // Base Case if (node == null) return; // Recur for right subtree first bottomRightViewUtil(node.right, level, max_level); // If this is the last Node of its level if (max_level.max_level < level) { document.write(node.data + " "); max_level.max_level = level; } // Recur for left subtree with increased level bottomRightViewUtil(node.left, level + 1, max_level);}// A wrapper over bottomRightViewUtil()function bottomRightView(node){ bottomRightViewUtil(node, 1, max);}// Driver Codevar root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.right.left = new Node(5);root.right.left.right = new Node(6);bottomRightView(root);// This code is contributed by rrrtnx.</script> |
Output
3 6 4
Time Complexity : O(N), where N is the number of nodes of the binary tree.
Auxiliary space: O(n) for implicit call stack as using recursion.
Iterative Approach:
C++
// C++ program to print// bottom right view of BT#include <bits/stdc++.h>using namespace std;// A binary Tree nodestruct Node { int data; Node *left, *right;};// create and returns a new nodeNode* newNode(int val){ Node* temp = new Node(); temp->data = val; temp->left = temp->right = NULL; return temp;}// fun to print bottom right view of a BTvoid bottomRightView(Node* root){ // Base case if (!root) return; queue<Node*> q; q.push(root); while (!q.empty()) { int size = q.size(); while (size--) { root = q.front(); q.pop(); // traverse all right nodes and push leftnodes // (if any) into the queue for the next level // traverse while (root->right) { if (root->left) q.push(root->left); root = root->right; } // if last node has any left node if (root->left) q.push(root->left); } // print the data cout << root->data << " "; }}int main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->right->left = newNode(5); root->right->left->right = newNode(6); bottomRightView(root); return 0;}// This code is contributed by Modem Upendra. |
Java
// Java code for the above approachimport java.util.*;public class GFG { // A binary Tree node static class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } // create and returns a new node static Node newNode(int val) { Node temp = new Node(val); return temp; } // fun to print bottom right view of a BT static void bottomRightView(Node root) { // Base case if (root == null) { return; } Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { int size = q.size(); while (size-- > 0) { root = q.poll(); // traverse all right nodes and push // leftnodes // (if any) into the queue for the next // level traverse while (root.right != null) { if (root.left != null) { q.add(root.left); } root = root.right; } // if last node has any left node if (root.left != null) { q.add(root.left); } } // print the data System.out.print(root.data + " "); } } // Driver Code public static void main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.left.right = newNode(6); bottomRightView(root); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program to print bottom right# view of a BT# A binary Tree nodeclass Node: def __init__(self, val): self.data = val self.left = None self.right = None# fun to print bottom right view of a BTdef bottomRightView(root): # Base case if not root: return q = [] q.append(root) while q: size = len(q) while size > 0: root = q.pop(0) # traverse all right nodes and push leftnodes # (if any) into the queue for the next level # traverse while root.right: if root.left: q.append(root.left) root = root.right # if last node has any left node if root.left: q.append(root.left) size -= 1 # print the data print(root.data, end=" ")# create and returns a new nodedef newNode(val): temp = Node(val) return temp#Driver coderoot = newNode(1)root.left = newNode(2)root.right = newNode(3)root.left.left = newNode(4)root.right.left = newNode(5)root.right.left.right = newNode(6)bottomRightView(root)#This code is contributed by Potta Lokesh |
C#
using System;using System.Collections;using System.Collections.Generic;public class Gfg{ public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; } } // create and returns a new node /*Node* newNode(int val) { Node* temp = new Node(); temp.data = val; temp.left = temp.right = NULL; return temp; }*/ // fun to print bottom right view of a BT static void bottomRightView(Node root) { // Base case if (root==null) return; Queue<Node> q=new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { int size = q.Count; while (size-->0) { root = q.Peek(); q.Dequeue(); // traverse all right nodes and push leftnodes // (if any) into the queue for the next level // traverse while (root.right != null) { if (root.left != null) q.Enqueue(root.left); root = root.right; } // if last node has any left node if (root.left != null) q.Enqueue(root.left); } // print the data Console.Write(root.data+" "); } } public static void Main(string[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.left.right = new Node(6); bottomRightView(root); }}// This code is contributed by poojaagarwal2. |
Javascript
<script>// Javascript program to print bottom// right view of BT// A binary tree nodeclass Node { constructor(item) { this.data = item; this.left = null; this.right = null; }}// Iterative function to print bottom// right view of a binary tree.function bottomRightView(root){ // Base Case if (root == null) return; var queue = []; queue.push(root); while (queue.length) { var size = queue.length; while(size--){ root = queue.shift(); while(root.right != null){ if(root.left != null) queue.push(root.left); root = root.right; } if(root.left != null) queue.push(root.left); } document.write(root.data + " "); }}// Driver Codevar root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.right.left = new Node(5);root.right.left.right = new Node(6);bottomRightView(root);// This code is contributed by Susobhan Akhuli</script> |
Output
3 6 4
Time Complexity: O(N), where N is the total nodes in a BT.
Auxiliary Space: O(n), where n is the maximum nodes possible in a diagonal.
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!
