WeAreBack
BAN USERThis is a question for Binary Search Tree.
So, we should make use of this fact.
Pseudocode::
**Do a binary Search to find the given node.
**Keep Track of a previous ancestor which has a right child and its level.
**If given node was a left child, its parent's right child will be its immediate right sibling,
**otherwise, its ancestor's right_child's leftmost node at the level of the given node will be its immediate right sibling.
Max Time: O(2*logn)
Space: O(1)
We will ignore all other digits and will keep searching till we find required digits or we reach the leaf node.
If we find all the digits till we reach the leaf or before, we will give all the numbers stored in that leaf node.
Since all numbers are sorted , we will have to search in all branches which have number less than the first digit of pattern..(pattern is also sorted.)
//The following function returns the index if the element is found otherwise -1
// Where a is the array, n is the number of elements and k is the required element.
int found( int a[], int n, int k)
{
int i = 0;
if( k < ( a[0]-n+1 ) || k > ( a[0]+n-1) )
return -1;
while( i < n) {
if( a[i] == k )
return i;
i = i + ( ( a[i] > k ) ? ( a[i]-k ) : ( k-a[i] ) );
}
}
hey,
- WeAreBack January 18, 2015can you please explain the logic ?