Sum of all odd nodes in the path connecting two given nodes | Binary Tree node ; Utitlity function to create a 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 None 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
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT node = Node ( ) NEW_LINE node . data = data NEW_LINE node . left = None NEW_LINE node . right = None NEW_LINE return node NEW_LINE DEDENT def getPath ( root , arr , x ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT arr . append ( root . data ) NEW_LINE if ( root . data == x ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( getPath ( root . left , arr , x ) or getPath ( root . right , arr , x ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT arr . pop ( ) NEW_LINE return False NEW_LINE DEDENT def sumOddNodes ( root , n1 , n2 ) : NEW_LINE INDENT path1 = [ ] NEW_LINE path2 = [ ] NEW_LINE getPath ( root , path1 , n1 ) NEW_LINE getPath ( root , path2 , n2 ) NEW_LINE intersection = - 1 NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE while ( i != len ( path1 ) or j != len ( path2 ) ) : NEW_LINE INDENT if ( i == j and path1 [ i ] == path2 [ j ] ) : NEW_LINE INDENT i = i + 1 NEW_LINE j = j + 1 NEW_LINE DEDENT else : NEW_LINE INDENT intersection = j - 1 NEW_LINE break NEW_LINE DEDENT DEDENT sum = 0 NEW_LINE i = len ( path1 ) - 1 NEW_LINE while ( i > intersection ) : NEW_LINE INDENT if ( path1 [ i ] % 2 != 0 ) : NEW_LINE INDENT sum += path1 [ i ] NEW_LINE DEDENT i = i - 1 NEW_LINE DEDENT i = intersection NEW_LINE while ( i < len ( path2 ) ) : NEW_LINE INDENT if ( path2 [ i ] % 2 != 0 ) : NEW_LINE INDENT sum += path2 [ i ] NEW_LINE DEDENT i = i + 1 NEW_LINE DEDENT return sum NEW_LINE DEDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . right = newNode ( 6 ) NEW_LINE node1 = 5 NEW_LINE node2 = 6 NEW_LINE print ( sumOddNodes ( root , node1 , node2 ) ) NEW_LINE