Interview Question

Software Engineer Interview

-Montreal, QC

Zenefits

Given a Binary Search Tree with integers at every node and an integer k, write code that decides whether or not there exists two nodes a and b such that a+b=k

AnswerAdd Tags

Interview Answers

6 Answers

1

can you please list some more questions

can you please list some more questions on

0

Pretty good solution listed above

Ali on

0

The solution mentioned above is O(n^2), because for every node, it is comparing value with all the nodes in Vals array. We can do better than this because we have BST, which is in sorted order. (For unsorted Binary tree, we should have sorted first in O(nlogn) and then searched O(nlogn). O(nlogn) solution - Traverse the BST with DFS (O(n)). For each node of value 'a' search for node of value "b = k - a". Searching in BST would be O(logn). Thus the solution becomes O(nlogn)

O(nlogn) Solution on

0

HashMap tracker = new HashMap(); public SumPair parseTree(Node node, int sum) { if (node == null) { return null; } SumPair pair = parseTree(node.left, sum); if (pair == null) { pair = parseTree(node.right, sum); } if (pair == null) { if (tracker.containsKey(node.data)) { pair = new SumPair(node, tracker.get(node.data)); } else { tracker.put(sum - node.data, node); } } return pair; }

Shravan on

0

With a node reference to left,right and parent, it can be done in O(n) Start at deep left with 2 node references at lowest node, value L. move one reference in DFS way until it find a node R >= K-L. if equal then we have a L and R then move the first reference to the next value in DFS, until node L > K-R repeat until last node is reached and L + R > K lot of micro-optimization possible (skip a whole node by going direct to parent when the parent is still lower than what we looking for)

Claude on

1

Something like this? (Untested) private class Node { public boolean ContainsSum(int k) { return ContainsSum_(k, new ArrayList()); } protected boolean ContainsSum_(int k, ArrayList vals) { for (int i : vals) { if (i + m_val == k) return true; } vals.add(m_val); return (m_right != null && m_right.ContainsSum_(k, vals)) || (m_left != null && m_left.ContainsSum_(k, vals)); } private int m_val; private Node m_left; private Node m_right; }

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.