Given a Binary Tree. The task is to find the maximum value among all of the right child nodes of the Binary Tree.
Note: If the tree does not contains any right child node or is empty, print -1.
Examples:
Input :
7
/ \
6 5
/ \ / \
4 3 2 1
Output : 5
All possible right child nodes are: {3, 5, 1}
out of which 5 is of the maximum value.
Input :
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
Output : 9
The idea is to recursively traverse the tree with inorder traversal and for every node:
- Check if the right child node exists.
- If yes, store it’s value in a temporary variable.
- Return the maximum among (current node’s right child node’s value, recursive call for left subtree, recursive call for right subtree).
Below is the implementation of the above approach:
C++
// CPP program to print maximum element// among all right child nodes#include <bits/stdc++.h>using namespace std;// A Binary Tree Nodestruct Node { int data; struct Node *left, *right;};// Utility function to create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to find maximum element// among all right child nodes using// Inorder Traversalint maxOfRightElement(Node* root){ // Temp variable int res = INT_MIN; // If tree is empty if (root == NULL) return -1; // If right child exists if (root->right != NULL) res = root->right->data; // Return maximum of three values // 1) Recursive max in right subtree // 2) Value in right child node // 3) Recursive max in left subtree return max({ maxOfRightElement(root->right), res, maxOfRightElement(root->left) });}// Driver Codeint main(){ // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Node* root = newNode(7); root->left = newNode(6); root->right = newNode(5); root->left->left = newNode(4); root->left->right = newNode(3); root->right->left = newNode(2); root->right->right = newNode(1); cout << maxOfRightElement(root); return 0;} |
Java
// Java implementation to print maximum element // among all right child nodesimport java.io.*; import java.util.*;// User defined node classclass Node { int data; Node left, right; // Constructor to create a new tree node Node(int key) { data = key; left = right = null; }}class GFG { static int maxOfRightElement(Node root) { // Temp variable int res = Integer.MIN_VALUE; // If tree is empty if (root == null) return -1; // If right child exists if (root.right != null) res = root.right.data; // Return maximum of three values // 1) Recursive max in right subtree // 2) Value in right child node // 3) Recursive max in left subtree return Math.max(maxOfRightElement(root.right), Math.max(res,maxOfRightElement(root.left))); } // Driver code public static void main(String args[]) { // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Node root = new Node(7); root.left = new Node(6); root.right = new Node(5); root.left.left = new Node(4); root.left.right = new Node(3); root.right.left = new Node(2); root.right.right = new Node(1); System.out.println(maxOfRightElement(root)); }}// This code is contributed by rachana soma |
Python3
# Python3 program to print maximum element# among all right child nodes# Tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None# Utility function to create a new tree nodedef newNode(data): temp = Node(0) temp.data = data temp.left = temp.right = None return temp# Function to find maximum element# among all right child nodes using# Inorder Traversaldef maxOfRightElement(root): # Temp variable res = -999999 # If tree is empty if (root == None): return -1 # If right child exists if (root.right != None): res = root.right.data # Return maximum of three values # 1) Recursive max in right subtree # 2) Value in right child node # 3) Recursive max in left subtree return max( maxOfRightElement(root.right), res, maxOfRightElement(root.left) )# Driver Code# Create binary tree# as shown below# 7# / \# 6 5# / \ / \# 4 3 2 1 root = newNode(7)root.left = newNode(6)root.right = newNode(5)root.left.left = newNode(4)root.left.right = newNode(3)root.right.left = newNode(2)root.right.right = newNode(1)print (maxOfRightElement(root))# This code is contributed by Arnab Kundu |
C#
// C# implementation to print maximum element // among all right child nodes using System;// User defined node class public class Node { public int data; public Node left, right; // Constructor to create a new tree node public Node(int key) { data = key; left = right = null; } } public class GFG { static int maxOfRightElement(Node root) { // Temp variable int res = int.MinValue; // If tree is empty if (root == null) return -1; // If right child exists if (root.right != null) res = root.right.data; // Return maximum of three values // 1) Recursive max in right subtree // 2) Value in right child node // 3) Recursive max in left subtree return Math.Max(maxOfRightElement(root.right), Math.Max(res,maxOfRightElement(root.left))); } // Driver code public static void Main(String []args) { // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Node root = new Node(7); root.left = new Node(6); root.right = new Node(5); root.left.left = new Node(4); root.left.right = new Node(3); root.right.left = new Node(2); root.right.right = new Node(1); Console.WriteLine(maxOfRightElement(root)); } } // This code is contributed 29AjayKumar |
Javascript
<script> // JavaScript implementation to print maximum element // among all right child nodes // User defined node class class Node { constructor(key) { this.left = null; this.right = null; this.data = key; } } function maxOfRightElement(root) { // Temp variable let res = Number.MIN_VALUE; // If tree is empty if (root == null) return -1; // If right child exists if (root.right != null) res = root.right.data; // Return maximum of three values // 1) Recursive max in right subtree // 2) Value in right child node // 3) Recursive max in left subtree return Math.max(maxOfRightElement(root.right), Math.max(res,maxOfRightElement(root.left))); } // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ let root = new Node(7); root.left = new Node(6); root.right = new Node(5); root.left.left = new Node(4); root.left.right = new Node(3); root.right.left = new Node(2); root.right.right = new Node(1); document.write(maxOfRightElement(root));</script> |
Output
5
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space: O(n)
Iterative Approach(Using Level Order Traversal):
Follow the below steps to solve the above problem
1) Return -1 if root node is NULL or root->right node is NULL.
2) Perform Level Order Traversal and check at each node if right node is exist then store the maximum of ans and current->node->right node data in ans.
3) Finally after completely traversing return the res.
Below is the implementation of above approach:
C++
// Iterative Approach to solve this problem// C++ code for above approach// This code is contributed by Yash Agarwal(yashagarwal2852002)#include<bits/stdc++.h>using namespace std;// a binary tree nodestruct Node{ int data; Node* left; Node* right; Node(int data){ this->data = data; this->left = NULL; this->right = NULL; }};// utility function to create a new tree nodeNode* newNode(int data){ return new Node(data);}// Function to find maximum element// among all right child nodes using// Level Order Traversalint maxOfRightElement(Node* root){ // temp variable int res = INT_MIN; // if tree is empty if(root == NULL) return -1; // if right child exists if(root->right == NULL) return -1; queue<Node*> q; q.push(root); while(!q.empty()){ Node* front_node = q.front(); q.pop(); if(front_node->left != NULL){ q.push(front_node->left); } if(front_node->right != NULL){ q.push(front_node->right); res = max(res, front_node->right->data); } } return res;}// Driver Codeint main(){ // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Node* root = newNode(7); root->left = newNode(6); root->right = newNode(5); root->left->left = newNode(4); root->left->right = newNode(3); root->right->left = newNode(2); root->right->right = newNode(1); cout << maxOfRightElement(root); return 0;}// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Java
// Java program for the above approachimport java.util.*;class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; }}class GFG { // Function to find maximum element // among all right child nodes using // Level Order Traversal static int maxOfRightElement(Node root) { // temp variable int res = Integer.MIN_VALUE; // if tree is empty if (root == null) return -1; // if right child exists if (root.right == null) return -1; Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { Node front_node = q.poll(); if (front_node.left != null) { q.add(front_node.left); } if (front_node.right != null) { q.add(front_node.right); res = Math.max(res, front_node.right.data); } } return res; } // Driver Code static public void main(String[] args) { // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Node root = new Node(7); root.left = new Node(6); root.right = new Node(5); root.left.left = new Node(4); root.left.right = new Node(3); root.right.left = new Node(2); root.right.right = new Node(1); System.out.println(maxOfRightElement(root)); }}// This code is contributed by codebraxnzt |
Python
# Iterative approach to solve self problem# Python code for the above approach# a binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None # utility function to create a new tree nodedef newNode(data): return Node(data)# function to find maximum element# among all right child nodes using# Level Order Traversaldef maxOfRightElement(root): # temp variable res = -10000000 # if tree is empty if(root is None): return -1 # if right child exists if(root.right is None): return -1 q = [] q.append(root) while(len(q) > 0): front_node = q.pop(0) if(front_node.left is not None): q.append(front_node.left) if(front_node.right is not None): q.append(front_node.right) res = max(res, front_node.right.data) return res# driver program to test above functionroot = newNode(7)root.left = newNode(6)root.right = newNode(5)root.left.left = newNode(4)root.left.right = newNode(3)root.right.left = newNode(2)root.right.right = newNode(1)print(maxOfRightElement(root)) |
C#
// C# code for iterative approach to solve this problem// This code is contributed by ChatGPTusing System;using System.Collections.Generic;// A binary tree nodeclass Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; }}class GFG { // Function to find maximum element // among all right child nodes using // Level Order Traversal static int maxOfRightElement(Node root) { // temp variable int res = int.MinValue; // if tree is empty if (root == null) return -1; // if right child exists if (root.right == null) return -1; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count > 0) { Node front_node = q.Dequeue(); if (front_node.left != null) { q.Enqueue(front_node.left); } if (front_node.right != null) { q.Enqueue(front_node.right); res = Math.Max(res, front_node.right.data); } } return res; } // Driver Code static public void Main() { // Create binary tree // as shown below /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Node root = new Node(7); root.left = new Node(6); root.right = new Node(5); root.left.left = new Node(4); root.left.right = new Node(3); root.right.left = new Node(2); root.right.right = new Node(1); Console.WriteLine(maxOfRightElement(root)); }} |
Javascript
// JavaScript implementation of above approach// a binary tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// utility functionto create a new nodefunction newNode(data){ return new Node(data);}// Function to find maximum element// among all right child nodes using// Level Order Traversalfunction maxOfRightElement(root){ // temp variable let res = Number.MIN_VALUE; // if tree is empty if(root == null) return -1; // if right child exists if(root.right == null) return -1; let q = []; q.push(root); while(q.length > 0){ let front_node = q.shift(); if(front_node.left != null) q.push(front_node.left); if(front_node.right != null){ q.push(front_node.right) res = Math.max(res, front_node.right.data); } } return res;}// driver code to test above function// Create binary tree// as shown below/* 7 / \ 6 5 / \ / \ 4 3 2 1 */ let root = newNode(7); root.left = newNode(6); root.right = newNode(5); root.left.left = newNode(4); root.left.right = newNode(3); root.right.left = newNode(2); root.right.right = newNode(1); console.log(maxOfRightElement(root)); |
Output
5
Time Complexity : O(N), where N is the number of nodes.
Auxiliary Space: O(N), due to queue data structure.
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!
