Hindhustani Posted December 30, 2021 Report Share Posted December 30, 2021 public class BinaryTree_2 { Node root; boolean hasPathSum(Node node, int sum) { boolean ans = false; int subSum = sum - node.data; if(subSum == 0 && node.left == null && node.right == null){ System.out.println("subSum ******* "+subSum); return true; } if(node.left != null) { System.out.println("Left ******* "+node.left.data); ans = ans || hasPathSum(node.left, subSum); } if(node.right != null) { // But if it is true then we can avoid calling hasPathSum // here as answer has already been found System.out.println( "Right ******* "+node.right.data ); ans = ans || hasPathSum(node.right, subSum); } return(ans); } // Driver Code public static void main(String args[]) { int sum = 21; /* Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2 */ BinaryTree_2 tree = new BinaryTree_2(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(6); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.left = new Node(2); if (tree.hasPathSum(tree.root, sum)) System.out.println( "There is a root to leaf path with sum " + sum); else System.out.println( "There is no root to leaf path with sum " + sum); } } output: Left ******* 8 Left ******* 3 subSum ******* 0 ——> ####at this line why method is not returning but still executing below if condition?#### Right ******* 5 Right ******* 6 There is a root to leaf path with sum 21 Quote Link to comment Share on other sites More sharing options...
ysshakeela Posted December 30, 2021 Report Share Posted December 30, 2021 1 hour ago, Hindhustani said: public class BinaryTree_2 { Node root; boolean hasPathSum(Node node, int sum) { boolean ans = false; int subSum = sum - node.data; if(subSum == 0 && node.left == null && node.right == null){ System.out.println("subSum ******* "+subSum); return true; } if(node.left != null) { System.out.println("Left ******* "+node.left.data); ans = ans || hasPathSum(node.left, subSum); } if(node.right != null) { // But if it is true then we can avoid calling hasPathSum // here as answer has already been found System.out.println( "Right ******* "+node.right.data ); ans = ans || hasPathSum(node.right, subSum); } return(ans); } // Driver Code public static void main(String args[]) { int sum = 21; /* Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2 */ BinaryTree_2 tree = new BinaryTree_2(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(6); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.left = new Node(2); if (tree.hasPathSum(tree.root, sum)) System.out.println( "There is a root to leaf path with sum " + sum); else System.out.println( "There is no root to leaf path with sum " + sum); } } output: Left ******* 8 Left ******* 3 subSum ******* 0 ——> ####at this line why method is not returning but still executing below if condition?#### Right ******* 5 Right ******* 6 There is a root to leaf path with sum 21 Where is the class definition of Node baa? Quote Link to comment Share on other sites More sharing options...
ysshakeela Posted December 30, 2021 Report Share Posted December 30, 2021 Ok I can interpret like this public class Node { Node(int data) { this.data = data; } Node left; Node right; int data = 0; } Quote Link to comment Share on other sites More sharing options...
Gowtham7777 Posted December 30, 2021 Report Share Posted December 30, 2021 some unfinished function call are executed. like after return hasPathSum is finished from its previous call. ex: ans = ans || hasPathSum(node.left, subSum); once its returns true this continues next line if(node.right != null) { Quote Link to comment Share on other sites More sharing options...
ysshakeela Posted December 30, 2021 Report Share Posted December 30, 2021 1 hour ago, Hindhustani said: public class BinaryTree_2 { Node root; boolean hasPathSum(Node node, int sum) { boolean ans = false; int subSum = sum - node.data; if(subSum == 0 && node.left == null && node.right == null){ System.out.println("subSum ******* "+subSum); return true; } if(node.left != null) { System.out.println("Left ******* "+node.left.data); ans = ans || hasPathSum(node.left, subSum); } else if(node.right != null) { // But if it is true then we can avoid calling hasPathSum // here as answer has already been found System.out.println( "Right ******* "+node.right.data ); ans = ans || hasPathSum(node.right, subSum); } return(ans); } // Driver Code public static void main(String args[]) { int sum = 21; /* Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2 */ BinaryTree_2 tree = new BinaryTree_2(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(6); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.left = new Node(2); if (tree.hasPathSum(tree.root, sum)) System.out.println( "There is a root to leaf path with sum " + sum); else System.out.println( "There is no root to leaf path with sum " + sum); } } output: Left ******* 8 Left ******* 3 subSum ******* 0 ——> ####at this line why method is not returning but still executing below if condition?#### Right ******* 5 Right ******* 6 There is a root to leaf path with sum 21 Add this: "else if(node.right != null) {" instead of " if(node.right != null) {" inside the method hasPathSum(..) Quote Link to comment Share on other sites More sharing options...
Hindhustani Posted December 30, 2021 Author Report Share Posted December 30, 2021 15 minutes ago, Gowtham7777 said: some unfinished function call are executed. like after return hasPathSum is finished from its previous call. ex: ans = ans || hasPathSum(node.left, subSum); once its returns true this continues next line if(node.right != null) { Bro , my understanding is that it should return and exit from method when there is a return statement condition met .. first time I’m seeing the scenario like this .. can you help me to explain more @Gowtham7777 Quote Link to comment Share on other sites More sharing options...
Gowtham7777 Posted December 30, 2021 Report Share Posted December 30, 2021 2 minutes ago, Hindhustani said: Bro , my understanding is that it should return and exit from method when there is a return statement condition met .. first time I’m seeing the scenario like this .. can you help me to explain more @Gowtham7777 you are missing this : hasPathSum function is calling itself... like hasPathSum -> hasPathSum so if return true, second func is done, first one is continuing its execution if you still didn't get it let me know... google for function recursion examples... Quote Link to comment Share on other sites More sharing options...
Hindhustani Posted December 30, 2021 Author Report Share Posted December 30, 2021 19 minutes ago, ysshakeela said: Add this: "else if(node.right != null) {" instead of " if(node.right != null) {" inside the method hasPathSum(..) Thanks bro but even with if statement when the return condition satisfies why it is not returns? Quote Link to comment Share on other sites More sharing options...
quickgun_murugun Posted December 30, 2021 Report Share Posted December 30, 2021 1 hour ago, Hindhustani said: public class BinaryTree_2 { Node root; boolean hasPathSum(Node node, int sum) { boolean ans = false; int subSum = sum - node.data; if(subSum == 0 && node.left == null && node.right == null){ System.out.println("subSum ******* "+subSum); return true; } if(node.left != null) { System.out.println("Left ******* "+node.left.data); ans = ans || hasPathSum(node.left, subSum); } if(node.right != null) { // But if it is true then we can avoid calling hasPathSum // here as answer has already been found System.out.println( "Right ******* "+node.right.data ); ans = ans || hasPathSum(node.right, subSum); } return(ans); } // Driver Code public static void main(String args[]) { int sum = 21; /* Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2 */ BinaryTree_2 tree = new BinaryTree_2(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(6); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.left = new Node(2); if (tree.hasPathSum(tree.root, sum)) System.out.println( "There is a root to leaf path with sum " + sum); else System.out.println( "There is no root to leaf path with sum " + sum); } } output: Left ******* 8 Left ******* 3 subSum ******* 0 ——> ####at this line why method is not returning but still executing below if condition?#### Right ******* 5 Right ******* 6 There is a root to leaf path with sum 21 Cool Quote Link to comment Share on other sites More sharing options...
Hindhustani Posted December 30, 2021 Author Report Share Posted December 30, 2021 5 minutes ago, Gowtham7777 said: you are missing this : hasPathSum function is calling itself... like hasPathSum -> hasPathSum so if return true, second func is done, first one is continuing its execution if you still didn't get it let me know... google for function recursion examples... Thank you bro, I got it .. how much exp you have in Java? It’s been years I did coding trying to brush skills .. Quote Link to comment Share on other sites More sharing options...
Gowtham7777 Posted December 30, 2021 Report Share Posted December 30, 2021 10 minutes ago, Hindhustani said: Thank you bro, I got it .. how much exp you have in Java? It’s been years I did coding trying to brush skills .. this is not java concept, this is programming stuff... from my experience I never used recursions in live projects... mostly for interviews only..... coming to java, If you looking for job in java they are lot of other things you need to focus.... 1 Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.