CareerCup

How are elements inserted in an array?
Is it in postorder, preorder, inorder or levelorder?

The next largest number is giong to be the smallst element of the tree rooted at its right child. Say the given number is at index i, get the right child from arr[2i+2]. New index is j = 2i+2;
keep looking for leftmost child arr[2j+1] untill arr[2j+1] is invalid. Next largest number would be arr[j];
But this is not in constant time :(

next largest no: is the successor of given number..

if n is leaf or if it has only left child..then its parent is the successor..
else
move to right node and take left till v reach leaf..then this leaf node is its successor

I suppose that the BST is a complete tree and the indices are 0-based.
Say the given number is at index i. There are several cases we need to check:

1) If this node has a right child, so the sought node should be the leftmost node of the right subtree.
2) If this node hasn't a right child and it is a left child, so the parent node is the sought node.
3) If this node hasn't a right child and it is a right child, so we need to find the first parent which is a left child, and it's parent should be the sought node.

In all cases we can do some calculations (O(1)) in order to find the sought node.

1) The existence of the right child could be done with the following condition:
bool isRightChildExists = (2*i+2 < N), where N is the number of node in the tree. Now we must find the leftmost nodes index. this node should be located on the last or previous level. The hight of the tree is [log(N+1)] (say root is located on the 0 level) and the i-th node's level is [log(i+1)]. The root of the right subtree is 2*i+2 so we need to find the (d = [log(N+1)]-[log(i+1)]-1) d-th left child. It is also easy to see that the n-th left node's index could be found as follows: (2^(n+1))*(i+1)-1. So the sought node's index should be (2^(d+1))*((2*i+2)+1)-1. If this value is > N, so the sought node is located on the previous level and it's index is calculated in the same way, just by replacing d with d-1.

2) All left child's indices are odd, so if (i&1 != 0) then the sought node's index is [(i-1)/2].

3) The n-th (n>1) right child of the i-th node could be found as follows: (2^n)*(i+2)-2. So we need to find the maximum n for which there is some x (the first left child parent of i-th node) when (2^n)*(x+2)-2=i. That is i-th node is the n-th right child.
Therefore x=(i+2)/(2^n)-2. Easy to see that n is the greatest for which i+2 could be divided to 2^n. If we write the i+2 in the binary format, then the number of the last 0-s should the n. So 2^n=((i+2)xor(i+1))+1. Then x=(i+2)/(((i+2)xor(i+1))-1). The sought node is the parent of x: [(x-1)/2].

Any comments are welcome.

Hi All

When an BST is implemented in an array. It is stored as level order. So on this condsideration. If we are given the index of the element. Say we have an array of node objest. Which has a data in it.

Now every elements child will be @ 2i and 2i+1st element in the array.
given an index i. find if the 2i+i th indexed element is null or not.
Case1 it is not null// has a right child
i = 2i+1;
while(arr[i]!=null)// geting the leftmost child of right sub tree.
i = 2*i;

return arr[tmp];

Case2 2i+1 is null // no child

while((i%2) == 1 )// checking if current index is right child or not
i=i/2;

return arr[i];

this is a inorder successor finding question i think

i dont get how they will store a BST in a array....normally array is used for heaps which are complete binary trees....for BST some nodes may be missing left/right childs....so if that is the case we have to assume that there is a value for node does not exist....can think of a constant time solution....O(n) can be like this

find_next_greater(given_number)
{
index=find_index(given_number);
if (array[2*index+1])==NAN //for null node 
   { return error("number has no larger number");}
else if(array[2*(2*index+1)]!=NAN)
   {find_next_greater(array[2*index+1]);}//assuming 2*i+1 is rchild and 2*i is lchild
else
   {print("next number is",array[2*index+1] ); exit;}
}