APill
BAN USERSince no extra space is allowed, I did an inorder traversal to find the first node. Substracted that from the sum to determine the expected value for the second node. This I then passed to another method that does an inorder traversal to find the second node. If the second node is found then yes a sum exists. Efficiency is O(n2).
public boolean hasSummationNodes(Node node, int sum) {
return inorderFirstNode(node, sum);
}
public boolean inorderFirstNode(Node node, int sum) {
if (node == null) {
return false;
}
boolean foundLeft = inorderFirstNode(node.leftChild, sum);
int value = sum - node.data;
boolean found = inorderSecondNode(root, value);
boolean foundRight = inorderFirstNode(node.rightChild, sum);
return found | foundLeft | foundRight;
}
public boolean inorderSecondNode(Node node, int value) {
boolean found = false;
if (node == null) {
return false;
}
boolean foundLeft = inorderSecondNode(node.leftChild, value);
if (node.data == value) {
found = true;
}
boolean foundRight = inorderSecondNode(node.rightChild, value);
return found | foundLeft | foundRight;
}
1.Add a 0 to the array.
2. Sort the array ,
3. Find the location of 0 in the sorted array
4. Find the elements closes to 0..can be before or after
5. Return their sum
There is a edge case that a 0 already exists in which case you would slightly modify the logic to find the position of nearest values. I have not coded that. Time efficiency O(nLgn) for the sort and O(n) for iterating over the array. space complexity O(n).
- APill March 02, 2016