Find maximum value between two nodes in Binary tree

Given a binary tree and two nodes a and b, the task is to print the maximum node value that lies in the path connecting the nodes a and b. If either of the two nodes are not present in the tree then print -1.

Examples:

Input : 
          1
         /  \
        2    3
       / \    \
      4   5    6
         /    / \
        7    8   9

  a = 2 , b = 8

Output :8

Input :
          20
         /   \
        8     22
      /   \  /   \
     5     3 4    25
          / \
         10  14
   
  a = 3 , b = 4

Output :22

Approach: The idea is to find the LCA (i.e., Lowest Common Ancestor in a Binary Tree) of both the nodes. Then start searching for the maximum node in the path from LCA to first node and the maximum value in the path from LCA to second node, return the maximum of the two values which will be our answer. In case either of the nodes is not present in tree return -1.

Below is the implementation of the above approach:

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;

// Structure of binary tree
struct Node {
     Node* left;
     Node* right;
     int data;
};

// Function to create a new node
Node* newNode(int key)
{	 	
    Node* node = new Node();
 	node->left = node->right = NULL;
 	node->data = key;
 	return node;
}

// Finds the path from root node to given root of the tree, Stores the 
// path in a vector path[], returns true if path exists otherwise false
bool FindPath(Node* root ,vector<int> &path ,int key)
{
	if(root == NULL)
	return false;
	
	path.push_back(root->data);
	
	if(root->data == key)
	return true;
	
	if(FindPath(root->left ,path ,key) || FindPath(root->right ,path ,key))
	return true;
	
	path.pop_back();
	return false;
}

// Function that returns the maximum value present
// in the path connecting the given two nodes in binary tree
// It returns -1 if either of the two nodes is not present in the tree
int MaximumNodeInPath(Node* root ,int a ,int b)
{
	// To store paths to a from the root
	vector<int> Path1;
	
	// To store paths to b from the root
	vector<int> Path2;
	
	// To store the maximum value in the path
	int max_node = -1;
	
	// To store the maximum value in the path from LCA to a
	int max1 = -1;
	
	// To store the maximum value in the path from LCA to b
	int max2 = -1;
	
	int i = 0;
	int j = 0;
	
	// If both a and b are present in the tree
	if(FindPath(root ,Path1 ,a) && FindPath(root ,Path2 ,b))
	{
		// Compare the paths to get the first different value 
		for(i = 0 ; i < Path1.size() && Path2.size() ; i++)
		{
			if(Path1[i] != Path2[i])
			{
				break;
			}
		}
		i--;
		j = i;
		
		// Find maximum value in path from LCA to a
		for(; i < Path1.size() ; i++)
		{
			if(max1 < Path1[i])
			max1 = Path1[i];
		}
		
		// Find maximum value in path from LCA to b
		for(; j < Path1.size() ; j++)
		{
			if(max2 < Path2[j])
			max2 = Path2[j];
		}
		
		// Answer will be the maximum of max value in first
		// path and second path
		max_node = max(max1 ,max2);
	}
	
	return max_node;
}

// Driver Code 
int main() 
{ 
    Node *root = newNode(20); 
    root->left = newNode(8); 
    root->right = newNode(22); 
    root->left->left = newNode(5); 
    root->left->right = newNode(3); 
    root->right->left = newNode(4); 
    root->right->right = newNode(25); 
    root->left->right->left = newNode(10); 
    root->left->right->right = newNode(14); 
    
    int a = 3;
    int b = 4;
    
    cout << MaximumNodeInPath(root ,a ,b) ;
	 
    return 0; 
}

Output:

	 	
22