Given a binary tree and two nodes of that binary tree. Find the sum of all nodes with odd values in the path connecting the two given nodes.
For Example: In the above binary tree, sum of all odd nodes in the path between the nodes 
and 
will be 5 + 1 + 3 = 9.
Source : Amazon Interview Experience on Campus
Approach : The idea is to first find the path between the two given nodes of the binary tree using the concept as discussed in: Print path between any two nodes.
Once, we have the path between the two given nodes, calculate sum of all the odd valued nodes in that path and print it.
Below is the implementation of the above approach:
C++
// C++ program to find sum of all odd nodes // in the path connecting two given nodes#include<bits/stdc++.h>using namespace std;// Binary Tree nodestruct Node{ int data; struct Node* left; struct Node* right;};// Utility function to create a // new Binary Tree nodestruct Node* newNode(int data){ struct Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; return node;}// Function to check if there is a path from root // to the given node. It also populates // 'arr' with the given path bool getPath(Node* root, vector<int>& arr, int x) { // if root is NULL // there is no path if (!root) return false; // push the node's value in 'arr' arr.push_back(root->data); // if it is the required node // return true if (root->data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (getPath(root->left, arr, x) || getPath(root->right, arr, x)) return true; // 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 arr.pop_back(); return false; } // Function to get the sum of odd nodes in the // path between any two nodes in a binary tree int sumOddNodes(Node* root, int n1, int n2) { // vector to store the path of // first node n1 from root vector<int> path1; // vector to store the path of // second node n2 from root vector<int> path2; getPath(root, path1, n1); getPath(root, path2, n2); int intersection = -1; // Get intersection point int i = 0, j = 0; while (i != path1.size() || j != path2.size()) { // Keep moving forward until no intersection // is found if (i == j && path1[i] == path2[j]) { i++; j++; } else { intersection = j - 1; break; } } int sum = 0; // calculate sum of ODD nodes from the path for (int i = path1.size() - 1; i > intersection; i--) if(path1[i]%2) sum += path1[i]; for (int i = intersection; i < path2.size(); i++) if(path2[i]%2) sum += path2[i]; return sum; } // Driver Codeint main(){ struct 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; cout<<sumOddNodes(root, node1, node2); return 0;} |
Java
// Java program to find sum of all odd nodes // in the path connecting two given nodes import java.util.*;class solution{// Binary Tree node static class Node { int data; Node left; Node right; } // Utility function to create a // new Binary Tree node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return node; } // Function to check if there is a path from root // to the given node. It also populates // 'arr' with the given path static boolean getPath(Node root, Vector<Integer> arr, int x) { // if root is null // there is no path if (root==null) return false; // push the node's value in 'arr' arr.add(root.data); // if it is the required node // return true if (root.data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (getPath(root.left, arr, x) || getPath(root.right, arr, x)) return true; // 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 arr.remove(arr.size()-1); return false; } // Function to get the sum of odd nodes in the // path between any two nodes in a binary tree static int sumOddNodes(Node root, int n1, int n2) { // vector to store the path of // first node n1 from root Vector<Integer> path1= new Vector<Integer>(); // vector to store the path of // second node n2 from root Vector<Integer> path2= new Vector<Integer>(); getPath(root, path1, n1); getPath(root, path2, n2); int intersection = -1; // Get intersection point int i = 0, j = 0; while (i != path1.size() || j != path2.size()) { // Keep moving forward until no intersection // is found if (i == j && path1.get(i) == path2.get(j)) { i++; j++; } else { intersection = j - 1; break; } } int sum = 0; // calculate sum of ODD nodes from the path 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; } // Driver Code 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)); } } |
Python3
# Python3 program to find sum of all odd nodes # in the path connecting two given nodes # Binary Tree node class Node: def __init__(self): self.data = 0 self.left = None self.right = None# Utility function to create a # Binary Tree node def newNode( data): node = Node() node.data = data node.left = None node.right = None return node # Function to check if there is a path from root # to the given node. It also populates # 'arr' with the given path def getPath(root, arr, x): # if root is None # there is no path if (root == None) : return False # push the node's value in 'arr' arr.append(root.data) # if it is the required node # return True if (root.data == x) : return True # else check whether the required node lies # in the left subtree or right subtree of # the current node if (getPath(root.left, arr, x) or getPath(root.right, arr, x)) : return True # 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 arr.pop() return False# Function to get the sum of odd nodes in the # path between any two nodes in a binary tree def sumOddNodes(root, n1, n2) : # vector to store the path of # first node n1 from root path1 = [] # vector to store the path of # second node n2 from root path2 = [] getPath(root, path1, n1) getPath(root, path2, n2) intersection = -1 # Get intersection point i = 0 j = 0 while (i != len(path1) or j != len(path2)): # Keep moving forward until no intersection # is found if (i == j and path1[i] == path2[j]): i = i + 1 j = j + 1 else : intersection = j - 1 break sum = 0 i = len(path1) - 1 # calculate sum of ODD nodes from the path while ( i > intersection ): if(path1[i] % 2 != 0): sum += path1[i] i = i - 1 i = intersection while ( i < len(path2) ): if(path2[i] % 2 != 0) : sum += path2[i] i = i + 1 return sum # Driver Code 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) node1 = 5node2 = 6 print(sumOddNodes(root, node1, node2)) # This code is contributed by Arnab Kundu |
C#
// C# program to find sum of all odd nodes // in the path connecting two given nodes using System;using System.Collections.Generic;class GFG{// Binary Tree node public class Node { public int data; public Node left; public Node right; } // Utility function to create a // new Binary Tree node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return node; } // Function to check if there is a path from // root to the given node. It also populates // 'arr' with the given path static Boolean getPath(Node root, List<int> arr, int x) { // if root is null // there is no path if (root == null) return false; // push the node's value in 'arr' arr.Add(root.data); // if it is the required node // return true if (root.data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (getPath(root.left, arr, x) || getPath(root.right, arr, x)) return true; // 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 arr.RemoveAt(arr.Count - 1); return false; } // Function to get the sum of odd nodes in the // path between any two nodes in a binary tree static int sumOddNodes(Node root, int n1, int n2) { // List to store the path of // first node n1 from root List<int> path1 = new List<int>(); // List to store the path of // second node n2 from root List<int> path2 = new List<int>(); getPath(root, path1, n1); getPath(root, path2, n2); int intersection = -1; // Get intersection point int i = 0, j = 0; while (i < path1.Count || j < path2.Count) { // Keep moving forward until // no intersection is found if ( i == j && path1[i] == path2[j]) { i++; j++; } else { intersection = j - 1; break; } } int sum = 0; // calculate sum of ODD nodes from the path for (i = path1.Count - 1; i > intersection; i--) if(path1[i] % 2 != 0) sum += path1[i]; for (i = intersection; i < path2.Count; i++) if(path2[i] % 2 != 0) sum += path2[i]; return sum; } // Driver Code 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; Console.Write(sumOddNodes(root, node1, node2)); } }// This code is contributed by Arnub Kundu |
Javascript
<script> // JavaScript program to find sum of all odd nodes // in the path connecting two given nodes // Binary Tree node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Utility function to create a // new Binary Tree node function newNode(data) { let node = new Node(data); return node; } // Function to check if there is a path from root // to the given node. It also populates // 'arr' with the given path function getPath(root, arr, x) { // if root is null // there is no path if (root==null) return false; // push the node's value in 'arr' arr.push(root.data); // if it is the required node // return true if (root.data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (getPath(root.left, arr, x) || getPath(root.right, arr, x)) return true; // 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 arr.pop(); return false; } // Function to get the sum of odd nodes in the // path between any two nodes in a binary tree function sumOddNodes(root, n1, n2) { // vector to store the path of // first node n1 from root let path1= []; // vector to store the path of // second node n2 from root let path2= []; getPath(root, path1, n1); getPath(root, path2, n2); let intersection = -1; // Get intersection point let i = 0, j = 0; while (i != path1.length || j != path2.length) { // Keep moving forward until no intersection // is found if (i == j && path1[i] == path2[j]) { i++; j++; } else { intersection = j - 1; break; } } let sum = 0; // calculate sum of ODD nodes from the path for (i = path1.length - 1; i > intersection; i--) if(path1[i]%2!=0) sum += path1[i]; for (i = intersection; i < path2.length; i++) if(path2[i]%2!=0) sum += path2[i]; return sum; } let 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); let node1 = 5; let node2 = 6; document.write(sumOddNodes(root, node1, node2)); </script> |
Output
9
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space : O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
