Monday, May 17, 2010

BST

given a bst of n nodes, find two nodes whose sum is equal to a number k in O(n) time and constant space
Pubblicato da a
Reazioni: 

1 comment:

  1. The standard sorted array code is to start from both ends and move two pointers in tandem based on whether their sum is greater than, or lesser than K.

    In the case of BST though, keeping the pointers to the nodes will mean storing the recursion stack as well. That's log(n) storage. Is that acceptable?

    Or is there a "pure" constant space solution that doesn't even take the recursion stack depth into account?

    ReplyDelete

Subscribe to: Post Comments (Atom)