Sum of all odd nodes in the path connecting two given nodes | Java program to find sum of all odd nodes in the path connecting two given nodes ; Binary Tree node ; Utitlity function to create a new Binary Tree node ; Function to check if there is a path from root to the given node . It also populates ' arr ' with the given path ; if root is null there is no path ; push the node ' s ▁ value ▁ in ▁ ' arr ' ; if it is the required node return true ; else check whether the required node lies in the left subtree or right subtree of the current node ; required node does not lie either in the left or right subtree of the current node Thus , remove current node ' s ▁ value ▁ from ▁ ▁ ' arr 'and then return false ; Function to get the sum of odd nodes in the path between any two nodes in a binary tree ; vector to store the path of first node n1 from root ; vector to store the path of second node n2 from root ; Get intersection point ; Keep moving forward until no intersection is found ; calculate sum of ODD nodes from the path ; Driver Code
import java . util . * ; class solution { static class Node { int data ; Node left ; Node right ; } static Node newNode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = null ; node . right = null ; return node ; } static boolean getPath ( Node root , Vector < Integer > arr , int x ) { if ( root == null ) return false ; arr . add ( root . data ) ; if ( root . data == x ) return true ; if ( getPath ( root . left , arr , x ) || getPath ( root . right , arr , x ) ) return true ; arr . remove ( arr . size ( ) - 1 ) ; return false ; } static int sumOddNodes ( Node root , int n1 , int n2 ) { Vector < Integer > path1 = new Vector < Integer > ( ) ; Vector < Integer > path2 = new Vector < Integer > ( ) ; getPath ( root , path1 , n1 ) ; getPath ( root , path2 , n2 ) ; int intersection = - 1 ; int i = 0 , j = 0 ; while ( i != path1 . size ( ) || j != path2 . size ( ) ) { if ( i == j && path1 . get ( i ) == path2 . get ( j ) ) { i ++ ; j ++ ; } else { intersection = j - 1 ; break ; } } int sum = 0 ; for ( i = path1 . size ( ) - 1 ; i > intersection ; i -- ) if ( path1 . get ( i ) % 2 != 0 ) sum += path1 . get ( i ) ; for ( i = intersection ; i < path2 . size ( ) ; i ++ ) if ( path2 . get ( i ) % 2 != 0 ) sum += path2 . get ( i ) ; return sum ; } public static void main ( String args [ ] ) { Node root = newNode ( 1 ) ; root . left = newNode ( 2 ) ; root . right = newNode ( 3 ) ; root . left . left = newNode ( 4 ) ; root . left . right = newNode ( 5 ) ; root . right . right = newNode ( 6 ) ; int node1 = 5 ; int node2 = 6 ; System . out . print ( sumOddNodes ( root , node1 , node2 ) ) ; } }