Given a tree, the task is to find the maximum in an only left node of the binary tree.
Examples:
Input :
7
/ \
6 5
/ \ / \
4 3 2 1
Output : 6
Input :
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
Output : 8
Traverse with inorder traversal and Apply the condition for the left node only and get maximum of left node.
Implementation: Let’s try to understand with code.
C++
// CPP program to print maximum element// in left node.#include <bits/stdc++.h>using namespace std;// A Binary Tree Nodestruct Node { int data; struct Node *left, *right;};// Get max of left element using// Inorder traversalint maxOfLeftElement(Node* root){ int res = INT_MIN; if (root == NULL) return res; if (root->left != NULL) res = root->left->data; // Return maximum of three values // 1) Recursive max in left subtree // 2) Value in left node // 3) Recursive max in right subtree return max({ maxOfLeftElement(root->left), res, maxOfLeftElement(root->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;}// Driver program to test above functionsint main(){ // Let us create binary tree shown in above diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ cout << maxOfLeftElement(root); return 0;} |
Java
// Java program to print maximum element // in left node. import java.util.*;class GfG {// A Binary Tree Node static class Node { int data; Node left, right; }// Get max of left element using // Inorder traversal static int maxOfLeftElement(Node root) { int res = Integer.MIN_VALUE; if (root == null) return res; if (root.left != null) res = root.left.data; // Return maximum of three values // 1) Recursive max in left subtree // 2) Value in left node // 3) Recursive max in right subtree return Math.max(maxOfLeftElement(root.left), Math.max(res, maxOfLeftElement(root.right))); } // Utility function to create a new tree node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp; } // Driver program to test above functions public static void main(String[] args) { // Let us create binary tree shown in above diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ System.out.println(maxOfLeftElement(root)); }} |
Python3
# Python program to print maximum element # in left node. # Utility class to create a # new tree node class newNode: def __init__(self, data): self.data = data self.left = self.right = None # Get max of left element using # Inorder traversal def maxOfLeftElement(root): res = -999999999999 if (root == None): return res if (root.left != None): res = root.left.data # Return maximum of three values # 1) Recursive max in left subtree # 2) Value in left node # 3) Recursive max in right subtree return max({ maxOfLeftElement(root.left), res, maxOfLeftElement(root.right) })# Driver Codeif __name__ == '__main__': # Let us create binary tree shown # in above diagram 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) # 7 # / \ # 6 5 # / \ / \ # 4 3 2 1 print(maxOfLeftElement(root))# This code is contributed by PranchalK |
C#
// C# program to print maximum element // in left node.using System;class GfG { // A Binary Tree Node class Node { public int data; public Node left, right; } // Get max of left element using // Inorder traversal static int maxOfLeftElement(Node root) { int res = int.MinValue; if (root == null) return res; if (root.left != null) res = root.left.data; // Return maximum of three values // 1) Recursive max in left subtree // 2) Value in left node // 3) Recursive max in right subtree return Math.Max(maxOfLeftElement(root.left), Math.Max(res, maxOfLeftElement(root.right))); } // Utility function to create a new tree node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp; } // Driver code public static void Main(String[] args) { // Let us create binary tree // shown in above diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Console.WriteLine(maxOfLeftElement(root)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to print maximum element // in left node.// A Binary Tree Node class Node { constructor() { this.data = 0; this.left = null; this.right = null; }}// Get max of left element using // Inorder traversal function maxOfLeftElement(root) { var res = -1000000000; if (root == null) return res; if (root.left != null) res = root.left.data; // Return maximum of three values // 1) Recursive max in left subtree // 2) Value in left node // 3) Recursive max in right subtree return Math.max(maxOfLeftElement(root.left), Math.max(res, maxOfLeftElement(root.right))); } // Utility function to create a new tree node function newNode(data) { var temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp; } // Driver code // Let us create binary tree// shown in above diagram var 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */document.write(maxOfLeftElement(root)); </script> |
Output
6
Iterative Approach(using queue):
Follow the below steps to solve the given problem:
1). Perform level order traversal using queue data structure.
2). At each node check it’s left children is null or not. If the left children is not null then compare its with the existing max left value.
3). If the current node left child value is greater than the existing value then update the max left value with current node left child value.
Below is the implementation of above approach:
C++
// C++ Program to print maximum element// in left node#include<bits/stdc++.h>using namespace std;// a binary tree nodestruct Node{ int data; Node* left; Node* right;};// utiltity function to create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp;}// get max of left element by// level order traversal using queueint maxOfLeftElement(Node* root){ int res = INT_MIN; if(root == NULL) return res; queue<Node*> q; q.push(root); while(!q.empty()){ Node* front_node = q.front(); q.pop(); if(front_node->left != NULL){ res = max(res, front_node->left->data); } if(front_node->left) q.push(front_node->left); if(front_node->right) q.push(front_node->right); } return res;}// Driver program to test above functionsint main(){ // Let us create binary tree shown in above diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ cout << maxOfLeftElement(root); return 0;}// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Java
// Java program for the above approachimport java.util.*;// a binary tree nodeclass Node { int data; Node left; Node right; Node(int data) { this.data = data; left = right = null; }}class Main { // get max of left element by // level order traversal using queue static int maxOfLeftElement(Node root) { int res = Integer.MIN_VALUE; if(root == null) return res; Queue<Node> q = new LinkedList<Node>(); q.offer(root); while(!q.isEmpty()){ Node front_node = q.poll(); if(front_node.left != null){ res = Math.max(res, front_node.left.data); } if(front_node.left != null) q.offer(front_node.left); if(front_node.right != null) q.offer(front_node.right); } return res; } // Driver program to test above functions public static void main(String[] args) { // Let us create binary tree shown in above diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ System.out.println(maxOfLeftElement(root)); }}// This code is contributed by codebraxnzt |
Python3
from queue import Queue# a binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# get max of left element by level order traversal using queuedef maxOfLeftElement(root): res = float('-inf') if root is None: return res q = Queue() q.put(root) while not q.empty(): front_node = q.get() if front_node.left: res = max(res, front_node.left.data) if front_node.left: q.put(front_node.left) if front_node.right: q.put(front_node.right) return res# Driver program to test above functionsif __name__ == '__main__': # Let us create binary tree shown in above diagram root = Node(7) root.left = Node(6) root.right = Node(5) root.left.left = Node(4) root.left.right = Node(3) root.right.left = Node(2) root.right.right = Node(1) """ 7 / \ 6 5 / \ / \ 4 3 2 1 """ print(maxOfLeftElement(root)) |
C#
// C# Program to print maximum element// in left nodeusing System;using System.Collections.Generic;// a binary tree nodeclass Node{ public int data; public Node left; public Node right; public Node(int data){ this.data = data; left = null; right = null; }}class BinaryTree{ // get max of left element by // level order traversal using queue public static int maxOfLeftElement(Node root){ int res = int.MinValue; if(root == null) return res; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while(q.Count > 0){ Node front_node = q.Dequeue(); if(front_node.left != null){ res = Math.Max(res, front_node.left.data); } if(front_node.left != null) q.Enqueue(front_node.left); if(front_node.right != null) q.Enqueue(front_node.right); } return res; } // Driver program to test above functions static void Main(){ // Let us create binary tree shown in above diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ Console.WriteLine(maxOfLeftElement(root)); }} |
Javascript
// javascript Program to print maximum element// in left node// a binary tree nodeclass Node{ constructor(){ this.data = 0; this.left = null; this.right = null; }}// utiltity function to create a new tree nodefunction newNode(data){ let temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// get max of left element by// level order traversal using queuefunction maxOfLeftElement(root){ let res = -2000; if(root == null) return res; let q = []; q.push(root); while(q.length > 0){ let front_node = q[0]; q.shift(); if(front_node.left != null){ res = Math.max(res, front_node.left.data); } if(front_node.left) q.push(front_node.left); if(front_node.right) q.push(front_node.right); } return res;}// Driver program to test above functions// Let us create binary tree shown in above diagramlet 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);/* 7 / \ 6 5 / \ / \ 4 3 2 1 */console.log(maxOfLeftElement(root));// The code is contributed by Nidhi goel. |
Output
6
Time Complexity: O(N) where N is the number of nodes in given binary tree.
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!
