In a BST write a program to find 2 nodes x and y such that X+y=k

Question

Cliff · Accepted Answer

You can solve the problem in O(n) time.
First  you find the smallest number in the tree then you find the highest number (worst-case linear time, logarithmic time if the BST is balanced).
If their sum is larger than K, you find the largest number in the tree that is lower than y (you can do it in amortized constant time)
If their sum is lower than K, you find the smallest number in the tree that is higher than x
(amortized constant time).
And you continue this algorithm until you reach the correct X and Y :)

MessyHack · Answer

This problem requires the use of a map aka dictionary aka hashtable.

Visit a node

If the node data isn't in the map; add the data to the map.
Solve for what the other number should be; check if it's in the map.
if it is you're done...

otherwise keep searching.

Sigiloso · Answer

I think we need to do traversals and check for every node.

Sigiloso · Answer

For a given x traverse nodes upto x + y <= k.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas