code4ghana
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
You could store the nodes into a hastable with extra O(n) space.
Traverse the BST.
If node.value>k, visit only the left child of the node.
Else if n-k<n: check to see if n-k is in the hastable if not, put n into the hastable, visit the left child first, the the right.
Else: check to see if n-k is in the hashtable if not put n into visit right child first, then visit left child.
//of course in both else scenarios, if n-k is in the hashtable, you have found a pair and you can exit.
Runtime: this will be at most O(n) but it should be in practice ~O(lgn).
Comment hidden because of low score. Click to expand.
0
of 0 vote
Could you please explain your answer...and also I don't recall floor and ceiling being normal functions of a bst...
- code4ghana December 14, 2012Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
You can use a graph to represent it. And then run a DFS on it for cycle detection.
- code4ghana December 14, 2012