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 the std::max function from the algorithm library.
  • In the main function, we create the Binary Tree and call findMax 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