Get maximum left node in binary tree
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 Node struct Node { int data; struct Node *left, *right; }; // Get max of left element using // Inorder traversal int 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 node Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Driver program to test above functions int 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 Code if __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> |
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 node struct Node{ int data; Node* left; Node* right; }; // utiltity function to create a new tree node Node* 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 queue int 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 functions int 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 approach import java.util.*; // a binary tree node class 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 node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # get max of left element by level order traversal using queue def 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 functions if __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 node using System; using System.Collections.Generic; // a binary tree node class 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 node class Node{ constructor(){ this .data = 0; this .left = null ; this .right = null ; } } // utiltity function to create a new tree node function 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 queue function 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 diagram 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); /* 7 / \ 6 5 / \ / \ 4 3 2 1 */ console.log(maxOfLeftElement(root)); // The code is contributed by Nidhi goel. |
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.