searching if one of two keys is presented in binary search tree

[RyanC]

Hi everybody! it's really awesome to come back after a good while of learning C.

I have interfaced a problem in binary search tree, I've two keys given and want to search if any of two keys(OR) is presented in the binary search tree or not. what confusing me that I need to solve the problem in an optimal way, meaning I need the "time complexity/space" is much as lower as possible.

I can make an iterative way to search in binary search tree, and calls "twice to the function search for doing search", but is there any possible way for instance to search on the tree once and not twice for finding if one of two keys are presented or not?! thanks !!
just a note, every node in the binary search tree has field of one "data" ! it's like

struct node{
                                        int data;
                                        struct node* left, *right};

thanks in advance !

[RyanC]

it's much appreciated if you can attach by your answer a code to understand you very well ! thanks

[Salem]

Well your initial search is O(log₂(N)).

Searching twice is only 2x that, which makes no difference to the overall complexity.

But I suppose you could do d1 < data && d1 < data to find a lower common ancestor where you have to go left for one value and right for the other.

[RyanC]

Well your initial search is O(log₂(N)).

Searching twice is only 2x that, which makes no difference to the overall complexity.

But I suppose you could do d1 < data && d1 < data to find a lower common ancestor where you have to go left for one value and right for the other.

Alright, but didn't succeed in finding the lower common ancestor ! can you illustrate that by code? I'm not saying to code the binary tree and bla bla bla ... meaning just the part of "finding the lower ancestor" !

thanks

[Salem]

Presumably if you're searching for 2 keys, do you want two answers?

If you want both answers, there's little point in creating a massively bloated interface passing in two values, two result pointers and a node pointer.

If you're only after 'whichever is first', then 'first' is a vague notion depending on how you decide to traverse the tree.

if ( d1 < data && d2 < data ) goLeft
if ( d1 > data && d2 > data ) goRight
Otherwise, you've found the deepest common ancestor,
because you now need to follow left and right separately.

[RyanC]

Presumably if you're searching for 2 keys, do you want two answers?

If you want both answers, there's little point in creating a massively bloated interface passing in two values, two result pointers and a node pointer.

If you're only after 'whichever is first', then 'first' is a vague notion depending on how you decide to traverse the tree.

if ( d1 < data && d2 < data ) goLeft
if ( d1 > data && d2 > data ) goRight
Otherwise, you've found the deepest common ancestor,
because you now need to follow left and right separately.

thanks!