Longest Path with Same Values in a Binary Tree | C ++ program to find the length of longest path with same values in a binary tree . ; A binary tree node has data , pointer to left child and a pointer to right child ; Function to print the longest path of same values ; Recursive calls to check for subtrees ; Variables to store maximum lengths in two directions ; If curr node and it 's left child has same value ; If curr node and it 's right child has same value ; Driver function to find length of longest same value path ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Driver code ; Let us construct a Binary Tree 4 / \ 4 4 / \ \ 4 9 5
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int val ; struct Node * left , * right ; } ; int length ( Node * node , int * ans ) { if ( ! node ) return 0 ; int left = length ( node -> left , ans ) ; int right = length ( node -> right , ans ) ; int Leftmax = 0 , Rightmax = 0 ; if ( node -> left && node -> left -> val == node -> val ) Leftmax += left + 1 ; if ( node -> right && node -> right -> val == node -> val ) Rightmax += right + 1 ; * ans = max ( * ans , Leftmax + Rightmax ) ; return max ( Leftmax , Rightmax ) ; } int longestSameValuePath ( Node * root ) { int ans = 0 ; length ( root , & ans ) ; return ans ; } Node * newNode ( int data ) { Node * temp = new Node ; temp -> val = data ; temp -> left = temp -> right = NULL ; return temp ; } int main ( ) { Node * root = NULL ; root = newNode ( 4 ) ; root -> left = newNode ( 4 ) ; root -> right = newNode ( 4 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 9 ) ; root -> right -> right = newNode ( 5 ) ; cout << longestSameValuePath ( root ) ; return 0 ; }