@Abhishek:nice algo dude..
On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav wrote:
> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, otherwise, you
> will ultimately reach a leaf node say 'nd'
> 2. Now the two can
1. I think if the given tree is BST then this problem cannot be solved in
o(log n), It can be solved in o(n)
Reason: If the given BST is skewed with numbers inserted in either
ascending/descending order. Now the given number to be searched is the the
one which is the leaf node of a BST, then there
@atul yes sure why not...
On Sat, Aug 20, 2011 at 1:39 PM, Naman Mahor wrote:
> i think there will be three candidate..
> 1. TreeSuccessor(nd) 2. TreePredecessor(nd) 3. nd it self.
>
>
> On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> Hey i tried
i think there will be three candidate..
1. TreeSuccessor(nd) 2. TreePredecessor(nd) 3. nd it self.
On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav wrote:
> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, oth
can any 1 suggest an algo without global vars pls
On Sat, Aug 20, 2011 at 1:29 PM, Abhishek Yadav
wrote:
> yes you are right thanks for correcting me, there would be 3 canditates.
>
>
> On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil wrote:
>
>> @Abhishek:
>> Its not always that you reach a leaf t
yes you are right thanks for correcting me, there would be 3 canditates.
On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil wrote:
> @Abhishek:
> Its not always that you reach a leaf through the node.
> But still your logic seems correct.
> There would be 3 candidates for minimum:
> -->predecessor
> -
@Abhishek:
Its not always that you reach a leaf through the node.
But still your logic seems correct.
There would be 3 candidates for minimum:
-->predecessor
-->current node
-->successor.
On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav
wrote:
> No your solution is correct tooits just that in
No your solution is correct tooits just that in your solution number of
comparisons done with the original number are more, while in my solution
they get down to 2. otherwise complexities of both the solution would be
O(log n).
I am stressing on no. of comparisons because in these kind of quest
is there anything wrong in my algo?
do tell me.
On 20 August 2011 12:56, Abhishek Yadav wrote:
> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, otherwise, you
> will ultimately reach a leaf node say 'nd'
> 2. Now
Hey i tried it now and got to another solution
O(log n) solution:
1. try searching for the number , if found,return the node, otherwise, you
will ultimately reach a leaf node say 'nd'
2. Now the two candidates for the answer would be
1. TreeSuccessor(nd) 2. TreePredecessor(nd)
Now
why traverse the whole tree?
at each root keep the difference in a min_diff and min_ele.
if the entered value is less root then move to left or right.
repeat above two until whole tree is checked or min_diff becomes 0.
pseudo code:
min_diff = INF; // global variables
min_ele = 0;
find_min_diff(
yes, the interviewer said that there is a solution in O(log n)
On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan wrote:
> ur traversing the tree once so it shud be o(n).does the question demand
> 0(logn) ?
>
> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
ur traversing the tree once so it shud be o(n).does the question demand
0(logn) ?
On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav wrote:
> what would be the complexity of your solution O(n) or O(log n)..?
>
> On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan wrote:
>
>> traverse bst inorder and e
what would be the complexity of your solution O(n) or O(log n)..?
On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan wrote:
> traverse bst inorder and each time u encounter a node find the difference
> between the element and given element in question . if the absolute
> difference is minimum after
traverse bst inorder and each time u encounter a node find the difference
between the element and given element in question . if the absolute
difference is minimum after traversing the tree that is the element . u can
getback the element using another element which keeps sign of the element so
that
Given a BST and a number, Find the closest node to that number in the
BST. Give an algorithm for that.
Let there be binary search tree having nodes with values
12,34,64,23,64,25,76,6 and the number given is 28, then the answer
would be 25 as it is the closest node.
--
You received this message be
16 matches
Mail list logo
