Pages

Saturday, September 28, 2013

[Amazon interview Question] Calculate the weight of of binary tree path from root to leaf node in such a way that it would be equal to N

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
           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