You have a binary tree (no BST etc, a simple binary tree). A number N will be given to you, you have to find out, whether path from root node to leaf node exists in such a way so that sum of all node's data in that path is equal to N. For example for given binary tree
If value of N is 11 then path - 1 2 5 3 which is root node to left node 3 sums up to 11 hence for this tree method should return true.
Constraints: Time complexity is O(n) and space complexity should be O(1)
Method to implement : public boolean isSumTree(Node root, int N);
Please leave your valuable comments to improve my answer.
1 2 3 4 5 6 7 3 8 9
If value of N is 11 then path - 1 2 5 3 which is root node to left node 3 sums up to 11 hence for this tree method should return true.
Constraints: Time complexity is O(n) and space complexity should be O(1)
Method to implement : public boolean isSumTree(Node root, int N);
static class Node{ int data; Node left; Node right; } public static boolean isSumTree(Node root, int N){ if (root.left == null && root.right == null ){ return root.data == N; } boolean leftResult = root.left != null && isSumTree(root.left, N - root.data ); boolean rightResult = root.right != null && isSumTree(root.right, N - root.data ); return leftResult || rightResult; }
Please leave your valuable comments to improve my answer.
No comments:
Post a Comment