Table of Contents
Maximum in Binary Tree
Given a Binary Tree, write a function to find and return the maximum value among all nodes in the tree.
Sample Input:
Consider the following Binary Tree:
5
/ \
3 8
/ \ / \
2 4 6 10
Expected Output:
The maximum value in the Binary Tree is 10.
Time and Space Complexity:
The time complexity of finding the maximum value in a Binary Tree is O(n), where n is the number of nodes in the tree. This is because we need to visit every node once.
The space complexity is O(h), where h is the height of the tree, due to the space used by the recursive function call stack.
C++ Solution:
#include <iostream>
#include <algorithm> // Include the algorithm library for max function
// Define a node structure for the Binary Tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to find the maximum value in Binary Tree
int findMax(Node* root) {
if (root == nullptr)
return INT_MIN; // Initialize with smallest possible value
// Recursively find the maximum value in left and right subtrees
int leftMax = findMax(root->left);
int rightMax = findMax(root->right);
// Return the maximum of current node's value, left subtree's maximum, and right subtree's maximum
return std::max(root->data, std::max(leftMax, rightMax));
}
int main() {
// Creating the Binary Tree
Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(8);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(10);
// Find and print the maximum value in the Binary Tree
int maxValue = findMax(root);
std::cout << "Maximum value in Binary Tree: " << maxValue << std::endl;
return 0;
}
Code Explanation:
- We define a
Node
structure for the Binary Tree, holding data, a left child, and a right child. - The
findMax
function recursively finds the maximum value in the Binary Tree. For each node, it compares the node’s value with the maximum values of its left and right subtrees using thestd::max
function from the algorithm library. - In the
main
function, we create the Binary Tree and callfindMax
to calculate and print the maximum value in the tree.
When you run the code, it calculates and prints the maximum value in the given Binary Tree, which is 10 in this case.
Output:
Maximum value in Binary Tree: 10