CareerCup

First do a n = size+1...
Take binary representation of n.
Ignore MSB. Start from the MSB + 1th bit.
If 0 go left else go right.

Eg.

Node 1 --> Root
Node 2 --> 0010 --> Ignore leading one --> 0 -> L
Node 3 --> 0011 --> Ignore leading one --> 1 -> R

Node 10 --> 1010 --> Ignore leading one --> 010 --> L R L
Node 15 --> 1111 --> Ignore leading one --> 111 --> R R R
Node 9 --> 1001 --> Ignore leading one --> 001 --> L L R

@maryfan
it is not given as a complete binary tree..
only complete tree is given.
and size is also given
first of all find height h=[(log base 2)(size)]
now we have to find its pos in its level from the left
pos=(size-2^(h-1))
represent pos in binary appending zeros to the left to make it h digits
like something as 0100010..0110101
now start traversing from the root reading this binary num from the left using convension
0=left
1=right
you will reach your destination in O(log n) time

I am sorry...

1. The tree has no structure apart from being balanced
2. you have only access to those given structures
3. You have to position your insertion properly.


solution: Find no of levels, no of nodes in leaf level. Use a simple algorithm to position your insertion in leaf level. do the insertion...

sicne it is a complete binary tree.you can do insertion based on the binary values of the size.
1- 1
2 - 10
3 - 11
4 - 100


0 - for left and 1 - for right

if size is 4 then we need to insert the next in 100 position . that is root->left->left

Assumption:
1> Its a Complete Binary Tree (Binary is not mentioned and A node with two
pointers can be used for n-ary tree.So binary is not obvious from the
question)
2> Gneral convention of forming Complete tree from left to right is assumed.
This means when adding a child to a node, we'll add left child prior to
its right.

Algorithm with O(LogN) : (I've used Java style)

addNode(Tree t, TreeNode newNode) {
int n= t.size;
TreeNode p=t.root;
int ncomplete=0; //Stores the size of the Binary tree with root=p
//if it would have been completely full
int nPrevComplete=0; //stores size of the completely full BT with
//hight one less to ncomplete
int Lr=0; //Stores the no of nodes required to have
//ncomplete from nPrevComplete
int lr=0; //Actual nodes supplied to nPrevComplete

nPrevComplete=func(n); // func(X) returns an integer by changing all
//bits to the left of most significant bit of
//X to 1. Example func(5)=7
//This is to be done. Looking for O(1) time
//solution. Any HELP!!!!

while(n>2){
nComplete=nPrevComplete;
nPrevComplete=nPrevComplete>>>1 // Logical Right shift

LR=nComplete - nPrevComplete;
// As an enhancement this => LR=nComplete XOR nPrevComplete
lr=n - nPrevComplete;

if( (lr>= (LR/2)) && (lr<LR) ){ //Move to right of p
p=p.rChild;
n=(nPrevComplete -1)/2 + lr - (LR/2);
}else{ //Move to left of p
p=p.rChild;
n=(nPrevComplete -1)/2 + lr - (LR/2);
}
}

//p is the node whose child will be new node
//Giving preference to left child as a convention
if(p.lChild == null){
p.lChild=newNode;
}else{
p.rChild=newNode;
}
}//End of method

//Note, variables 'LR' and 'lr' are redandant and are used for ease of understanding

kq,
There is a cleaner way to do this. We assume we are dealing with a complete binary tree of length n and we are looking for the first empty node.

Let j be such that 2**j <= n < 2**(j+1). Express k=n-2**j in binary notation. Walk the tree to that first empty node by looking at k digit by digit. If the digit is 0 take the left tree, if it is 1 take the right tree.

The solution is neat but slightly wrong.2**j - 1 <=n<2**(j+1). k=n-(2**j-1).
For eg: If n=6 then j=2; Hence we have k= 6-2**2-1=3. This points to the location of the new node. Of course the no of digits to be considered is equal to j.

If each node has a only left and right nodes, it is a binary tree

logn - it's the height of the balanced tree. So to have insertion time O(logn) we should always have balanced tree.

The main idea behind the question is that,

1. the tree is not balanced.
2. you have only access to those given structures

How about doing a breath first traversal and inserting elements where there is no child?

let suppose tree size is n // where n is number of node.
2*i + 1 = n ( if n is odd )
2*i = n ( if n is even )
according to ...
i = n / 2 or n - 1 /2.

But can any one explain how this binary representation works for tree traversals?
Their relationship

doctorinterview.com/A/9A/9A23.html