Minimum and maximum node that lies in the path connecting two nodes in a Binary Tree | C ++ implementation of the approach ; Structure of binary tree ; Function to create a new node ; Function to store the path from root node to given node of the tree in path vector and then returns true if the path exists otherwise false ; Function to print the minimum and the maximum value present in the path connecting the given two nodes of the given binary tree ; To store the path from the root node to a ; To store the path from the root node to b ; To store the minimum and the maximum value in the path from LCA to a ; To store the minimum and the maximum value in the path from LCA to b ; If both a and b are present in the tree ; Compare the paths to get the first different value ; Find minimum and maximum value in the path from LCA to a ; Find minimum and maximum value in the path from LCA to b ; Minimum of min values in first path and second path ; Maximum of max values in first path and second path ; If no path exists ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { Node * left ; Node * right ; int data ; } ; Node * newNode ( int key ) { Node * node = new Node ( ) ; node -> left = node -> right = NULL ; node -> data = key ; return node ; } 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 ; } int minMaxNodeInPath ( Node * root , int a , int b ) { vector < int > Path1 ; vector < int > Path2 ; int min1 = INT_MAX ; int max1 = INT_MIN ; int min2 = INT_MAX ; int max2 = INT_MIN ; int i = 0 ; int j = 0 ; if ( FindPath ( root , Path1 , a ) && FindPath ( root , Path2 , b ) ) { for ( i = 0 ; i < Path1 . size ( ) && Path2 . size ( ) ; i ++ ) if ( Path1 [ i ] != Path2 [ i ] ) break ; i -- ; j = i ; for ( ; i < Path1 . size ( ) ; i ++ ) { if ( min1 > Path1 [ i ] ) min1 = Path1 [ i ] ; if ( max1 < Path1 [ i ] ) max1 = Path1 [ i ] ; } for ( ; j < Path2 . size ( ) ; j ++ ) { if ( min2 > Path2 [ j ] ) min2 = Path2 [ j ] ; if ( max2 < Path2 [ j ] ) max2 = Path2 [ j ] ; } cout << " Min ▁ = ▁ " << min ( min1 , min2 ) << endl ; cout << " Max ▁ = ▁ " << max ( max1 , max2 ) ; } else cout << " Max = -1 " ; } 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 = 5 ; int b = 1454 ; minMaxNodeInPath ( root , a , b ) ; return 0 ; }