Given a Binary Tree, find maximum(or minimum) element in it. For example, maximum in the following Binary Tree is 9.
In Binary Search Tree, we can find maximum by traversing right pointers until we reach rightmost node. But in Binary Tree, we must visit every node to figure out maximum. So the idea is to traverse the given tree and for every node return maximum of 3 values.
1) Node’s data.
2) Maximum in node’s left subtree.
3) Maximum in node’s right subtree.
Below is the implementation of above approach.
CPP
// C++ program to find maximum and
// minimum in a Bianry Tree
#include
#include
using namespace std;
// A tree node
class Node
{
public:
int data;
Node* left, *right;
/* Constructor that allocates a new
node with the given data and NULL
left and right pointers. */
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Returns maximum value in a given
// Binary Tree
int findMax(Node* root)
{
// Base case
if (root == NULL)
return INT_MIN;
// Return maximum of 3 values:
// 1) Root’s data 2) Max in Left Subtree
// 3) Max in right subtree
int res = root->data;
int lres = findMax(root->left);
int rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
// Driver Code
int main()
{
Node*NewRoot = NULL;
Node *root = new Node(2);
root->left = new Node(7);
root->right = new Node(5);
root->left->right = new Node(6);
root->left->right->left = new Node(1);
root->left->right->right = new Node(11);
root->right->right = new Node(9);
root->right->right->left = new Node(4);
cout << "Maximum element is " << findMax(root) << endl; return 0; } // This code is contributed by // rathbhupendra [tabby title="C"]
// C program to find maximum and minimum in a Bianry Tree #include <stdio.h> #include <stdlib.h> #include <limits.h> // A tree node struct Node { int data; struct Node* left, *right; }; // A utility function to create a new node struct Node* newNode(int data) { struct Node* node = (struct Node*) malloc(sizeof(struct Node)); node->data = data; node->left = node->right = NULL; return(node); } // Returns maximum value in a given Binary Tree int findMax(struct Node* root) { // Base case if (root == NULL) return INT_MIN; // Return maximum of 3 values: // 1) Root's data 2) Max in Left Subtree // 3) Max in right subtree int res = root->data; int lres = findMax(root->left); int rres = findMax(root->right); if (lres > res) res = lres; if (rres > res) res = rres; return res; } // Driver program int main(void) { struct Node*NewRoot=NULL; struct Node *root = newNode(2); root->left = newNode(7); root->right = newNode(5); root->left->right = newNode(6); root->left->right->left=newNode(1); root->left->right->right=newNode(11); root->right->right=newNode(9); root->right->right->left=newNode(4); printf ("Maximum element is %d
", findMax(root)); return 0; } |
Java
// Java code to Find maximum (or minimum) in // Binary Tree // A binary tree node class Node { int data; Node left, right; public Node(int data) { this.data = data; left = right = null; } } class BinaryTree { Node root; // Returns the max value in a binary tree static int findMax(Node node) { if (node == null) return Integer.MIN_VALUE; int res = node.data; int lres = findMax(node.left); int rres = findMax(node.right); if (lres > res) res = lres; if (rres > res) res = rres; return res; } /* Driver program to test above functions */ public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(2); tree.root.left = new Node(7); tree.root.right = new Node(5); tree.root.left.right = new Node(6); tree.root.left.right.left = new Node(1); tree.root.left.right.right = new Node(11); tree.root.right.right = new Node(9); tree.root.right.right.left = new Node(4); System.out.println("Maximum element is " + tree.findMax(tree.root)); } } // This code is contributed by Kamal Rawal |
Python3
# Python3 program to find maximum # and minimum in a Bianry Tree # A class to create a new node class newNode: def __init__(self, data): self.data = data self.left = self.right = None # Returns maximum value in a # given Binary Tree def findMax(root): # Base case if (root == None): return -999999999999 # Return maximum of 3 values: # 1) Root's data 2) Max in Left Subtree # 3) Max in right subtree res = root.data lres = findMax(root.left) rres = findMax(root.right) if (lres > res): res = lres if (rres > res): res = rres return res # Driver Code if __name__ == '__main__': root = newNode(2) root.left = newNode(7) root.right = newNode(5) root.left.right = newNode(6) root.left.right.left=newNode(1) root.left.right.right=newNode(11) root.right.right=newNode(9) root.right.right.left=newNode(4) print("Maximum element is", findMax(root)) # This code is contributed by PranchalK |
C#
using System; // C# code to Find maximum (or minimum) in // Binary Tree // A binary tree node public class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } public class BinaryTree { public Node root; // Returns the max value in a binary tree public static int findMax(Node node) { if (node == null) { return int.MinValue; } int res = node.data; int lres = findMax(node.left); int rres = findMax(node.right); if (lres > res) { res = lres; } if (rres > res) { res = rres; } return res; } /* Driver program to test above functions */ public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(2); tree.root.left = new Node(7); tree.root.right = new Node(5); tree.root.left.right = new Node(6); tree.root.left.right.left = new Node(1); tree.root.left.right.right = new Node(11); tree.root.right.right = new Node(9); tree.root.right.right.left = new Node(4); Console.WriteLine("Maximum element is " + BinaryTree.findMax(tree.root)); } } // This code is contributed by Shrikant13 |
Output:
Maximum element is 11
Similarly, we can find minimum element in Binary tree by comparing three values. Below is the function to find minimum in Binary Tree.
C
// Returns minimum value in a given Binary Tree int findMin(struct Node* root) { // Base case if (root == NULL) return INT_MAX; // Return minimum of 3 values: // 1) Root's data 2) Max in Left Subtree // 3) Max in right subtree int res = root->data; int lres = findMin(root->left); int rres = findMin(root->right); if (lres < res) res = lres; if (rres < res) res = rres; return res; } |
Java
// Returns the min value in a binary tree static int findMin(Node node) { if (node == null) return Integer.MAX_VALUE; int res = node.data; int lres = findMin(node.left); int rres = findMin(node.right); if (lres < res) res = lres; if (rres < res) res = rres; return res; } |
C#
// Returns the min value in a binary tree public static int findMin(Node node) { if (node == null) return int.MaxValue; int res = node.data; int lres = findMin(node.left); int rres = findMin(node.right); if (lres < res) res = lres; if (rres < res) res = rres; return res; } // This code is contributed by Code_Mech |
leave a comment
0 Comments