Given a binary tree and a target sum, determine whether there exists a root-to-leaf path in the tree such that the sum of the values of the nodes along the path is equal to the target sum when represented in binary, and the sum of the values of the nodes along the path is calculated by performing a bitwise AND operation between the binary representation of the values of each node in the path.
Examples:
Consider a binary tree with the following structure:
7
/ \
5 8
/ \ / \
15 13 12 16Input: Target_sum = 6
Output: False
Explanation: The binary representation of 6 is 110. If we perform the bitwise AND operation between the binary representation of the values of each node along the path from root to leaf, we never get 110 from any root-to-leaf path.Input: Target_sum = 5
Output: True
Explanation: The binary representation of 5 is 101. If we perform the bitwise AND operation between the binary representation of the values of {7, 5, 15} then we get 5.
Approach: This problem can be solved using a recursive depth-first search approach.
- Start from the root of the tree and perform a bitwise AND operation between the binary representation of the current node’s value and the previous result.
- Check if the current node is a leaf node and whether the current result is equal to the target sum in binary representation, if both conditions are satisfied, we return True.
- Otherwise, recursively traverse the left and right subtrees of the current node, passing the updated result to the next call.
- If no root-to-leaf path exists such that the sum of the values of the nodes along the path is equal to the target sum, the algorithm will return False.
Follow the steps to solve the problem:
- Create a function called hasPathSum that takes in a binary tree root and a target sum targetSum, and returns a boolean value indicating whether there exists a root-to-leaf path in the tree with the given condition.
- Create an inner function called dfs to traverse the binary tree recursively that takes in a node and the previous result, and returns a boolean value indicating whether there exists a root-to-leaf path in the subtree rooted at the given node with the given condition.
- Inside the dfs function, if the given node is NULL, return False.
- Calculate the current result by performing a bitwise AND operation between the previous result and the value of the current node.
- curr_result = prev_result & node->val.
- If the given node is a leaf node and the current result is equal to the target sum, return True.
- if (!node->left && !node->right), return curr_result == targetSum
- Recursively call the dfs function on the left and right subtrees with the updated current result.
- Return the OR of the results returned by the left and right subtree calls.
- Call the dfs function with the root node and an initial result of 0.
- Return the result returned by the dfs function.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodeclass TreeNode {public: int val; TreeNode* left; TreeNode* right; // constructor TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr) : val(val), left(left), right(right) { }};class GFG {public: bool hasPathSum(TreeNode* root, int targetSum) { // Define inner function dfs to // traverse the binary tree // recursively function<bool(TreeNode*, int)> dfs = [&](TreeNode* node, int prev_result) -> bool { // If node is NULL, return // false (base case) if (!node) return false; // Calculate the current // result by performing // bitwise AND operation // between previous result // and node value int curr_result = prev_result & node->val; // If node is a leaf node and // current result is equal to // targetSum, return true if (!node->left && !node->right) return curr_result == targetSum; // Recursively call dfs function // on left and right subtrees // with updated current result return dfs(node->left, curr_result) || dfs(node->right, curr_result); }; // Call the dfs function with root // node and initial result // of root value return dfs(root, root->val); }};// Drivers codeint main(){ // create a binary tree /* 7 / \ 5 8 / \ / \ 15 13 12 16 */ TreeNode* root = new TreeNode(7); root->left = new TreeNode(5); root->right = new TreeNode(8); root->left->left = new TreeNode(15); root->left->right = new TreeNode(13); root->right->left = new TreeNode(12); root->right->right = new TreeNode(16); // Create a solution object GFG obj; int target_sum = 6; // In this case, the target sum is 6 // which is represented in // binary as 110 if (obj.hasPathSum(root, target_sum)) cout << "True" << endl; // Else return False else cout << "False" << endl; target_sum = 5; // In this case, the target sum is 5 // which is represented in // binary as 101 if (obj.hasPathSum(root, target_sum)) cout << "True" << endl; else cout << "False" << endl; return 0;} |
Java
// Java program for the above approach// Definition for a binary tree node.class TreeNode { int val; TreeNode left; TreeNode right; // constructor TreeNode(int val) { this.val = val; left = null; right = null; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}class Solution { boolean dfs(TreeNode node, int prev_result, int targetSum) { // if node is null, return false (base case) if (node == null) return false; // calculate the current result by performing // bitwise AND operation between previous result // and node value int curr_result = prev_result & node.val; // if node is a leaf node and current result is // equal to targetSum, return true if (node.left == null && node.right == null) return curr_result == targetSum; // recursively call dfs function on left and // right subtrees with updated current result return dfs(node.left, curr_result, targetSum) || dfs(node.right, curr_result, targetSum); } public boolean hasPathSum(TreeNode root, int targetSum) { // define inner function dfs to traverse the binary // tree recursively // call the dfs function with root node and initial // result of root value return dfs(root, root.val, targetSum); }}// Example usagepublic class GFG { public static void main(String[] args) { // create a binary tree /* 7 / \ 5 8 / \ / \ 15 13 12 16 */ TreeNode root = new TreeNode(7); root.left = new TreeNode(5); root.right = new TreeNode(8); root.left.left = new TreeNode(15); root.left.right = new TreeNode(13); root.right.left = new TreeNode(12); root.right.right = new TreeNode(16); // create a solution object Solution sol = new Solution(); // In this case, the target sum is 6 // which is represented in binary as 110 if (sol.hasPathSum(root, 6)) System.out.println("True"); else System.out.println("False"); // False // In this case, the target sum is 5 // which is represented in binary as 101 if (sol.hasPathSum(root, 5)) System.out.println("True"); // True else System.out.println("False"); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python program for the above approach# Definition for a binary tree node.class TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = rightclass Solution: def hasPathSum(self, root: TreeNode, targetSum: int) -> bool: # define inner function dfs to traverse the binary # tree recursively def dfs(node, prev_result): # if node is None, return False (base case) if not node: return False # calculate the current result by performing # bitwise AND operation between previous result # and node value curr_result = prev_result & node.val # if node is a leaf node and current result is # equal to targetSum, return True if not node.left and not node.right: return curr_result == targetSum # recursively call dfs function on left and # right subtrees with updated current result return dfs(node.left, curr_result) or dfs(node.right, curr_result) # call the dfs function with root node and initial # result of root value return dfs(root, root.val)# Example usage# create a binary tree# 7# / \# 5 8# / \ / \# 15 13 12 16root = TreeNode(7)root.left = TreeNode(5)root.right = TreeNode(8)root.left.left = TreeNode(15)root.left.right = TreeNode(13)root.right.left = TreeNode(12)root.right.right = TreeNode(16)# create a solution objectsol = Solution()# In this case, the target sum is 6# which is represented in binary as 110print(sol.hasPathSum(root, 6)) # False# In this case, the target sum is 5# which is represented in binary as 101print(sol.hasPathSum(root, 5)) # True# This code is contributed by Susobhan Akhuli |
C#
// C# program for the above approachusing System;// Definition for a binary tree node.public class TreeNode { public int val; public TreeNode left; public TreeNode right; // constructor public TreeNode(int val) { this.val = val; left = null; right = null; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}public class Solution { public bool dfs(TreeNode node, int prev_result, int targetSum) { // if node is null, return false (base case) if (node == null) { return false; } // calculate the current result by performing // bitwise AND operation between previous result // and node value int curr_result = prev_result & node.val; // if node is a leaf node and current result is // equal to targetSum, return true if (node.left == null && node.right == null) { return curr_result == targetSum; } // recursively call dfs function on left and // right subtrees with updated current result return dfs(node.left, curr_result, targetSum) || dfs(node.right, curr_result, targetSum); } public bool HasPathSum(TreeNode root, int targetSum) { // define inner function dfs to traverse the binary // tree recursively // call the dfs function with root node and initial // result of root value return dfs(root, root.val, targetSum); }}// Example usagepublic class GFG { public static void Main(string[] args) { // create a binary tree /* 7 / \ 5 8 / \ / \ 15 13 12 16 */ TreeNode root = new TreeNode(7); root.left = new TreeNode(5); root.right = new TreeNode(8); root.left.left = new TreeNode(15); root.left.right = new TreeNode(13); root.right.left = new TreeNode(12); root.right.right = new TreeNode(16); // create a solution object Solution sol = new Solution(); // In this case, the target sum is 6 // which is represented in binary as 110 if (sol.HasPathSum(root, 6)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); // False } // In this case, the target sum is 5 // which is represented in binary as 101 if (sol.HasPathSum(root, 5)) { Console.WriteLine("True"); // True } else { Console.WriteLine("False"); } }}// This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript program for the above approach// Definition for a binary tree node.class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}class Solution { hasPathSum(root, targetSum) { // define inner function dfs to traverse the binary // tree recursively function dfs(node, prev_result) { // if node is None, return False (base case) if (!node) { return false; } // calculate the current result by performing // bitwise AND operation between previous result // and node value let curr_result = prev_result & node.val; // if node is a leaf node and current result is // equal to targetSum, return True if (!node.left && !node.right) { return curr_result == targetSum; } // recursively call dfs function on left and // right subtrees with updated current result return dfs(node.left, curr_result) || dfs(node.right, curr_result); } // call the dfs function with root node and initial // result of root value return dfs(root, root.val); }}// Example usage// create a binary tree// 7// / \// 5 8// / \ / \// 15 13 12 16let root = new TreeNode(7);root.left = new TreeNode(5);root.right = new TreeNode(8);root.left.left = new TreeNode(15);root.left.right = new TreeNode(13);root.right.left = new TreeNode(12);root.right.right = new TreeNode(16);// create a solution objectlet sol = new Solution();// In this case, the target sum is 6// which is represented in binary as 110console.log(sol.hasPathSum(root, 6)); // False// In this case, the target sum is 5// which is represented in binary as 101console.log(sol.hasPathSum(root, 5)); // True// This code is contributed by Tapesh(tapeshdua420) |
Output
False True
Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because we visit each node in the tree exactly once during the depth-first search.
Auxiliary Space: O(h), where h is the height of the binary tree. This is because the space used by the call stack during the depth-first search is proportional to the height of the tree. In the worst case, where the tree is skewed, the height of the tree can be equal to the number of nodes in the tree, giving a space complexity of O(N). However, in the best case, where the tree is perfectly balanced, the height of the tree is log(N), giving a space complexity of O(log(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!
Share your thoughts in the comments
