Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Empty binary tree and elements in array - Write a Program

Mustafa Garhi
Ranch Hand
Posts: 111
Hello ranchers ..

I was asked this question in an interview ..

Was a very interesting one ..

The officer told me there is an empty binary tree (structure unknown) and an array having elements.

I had to write a program that read the array in one go and filled the tree.

I could not give a very ideal solution but after i reached home and solved this, i found that a little thought and some coolness did it.

Now i want more such problems because i want to test my logic.

M looking for a product based company for a switch now and they ask such questions.

Has anyone got any reference to such coding problems?

Sony Agrawal
Ranch Hand
Posts: 143
What did you mean by
Mustafa Garhi wrote:read the array in one go

Mustafa Garhi
Ranch Hand
Posts: 111
I meant if the array size and the number of nodes in the tree are 10, No more than a loop of 10 should be used to read the array and write into the tree.

Sorry for that ambiguous statement. Hope its clear now.

Campbell Ritchie
Sheriff
Posts: 50251
79
You should be using a for-each loop which will guarantee to read each element in the array once.

Please show us how far you have got; we don't simply hand out code for such homework.

Sridhar Santhanakrishnan
Ranch Hand
Posts: 317
Please show us how far you have got; we don't simply hand out code for such homework.

I think Mustafa wants more homework

Mustafa Garhi
Ranch Hand
Posts: 111
Hey CR i don't need the code.

I need more such questions.

I have already solved the problem as i said :

Algorithm :

1) Sort the array in ascending order

2) Use
fill(Node node) {

if(node.leftChild!=null) {
fill(node.leftChild);
}

node.value = sortedArr[i++];

if(node.rightChild!=null) {
fill(node.rightChild);
}

Initially call fill with the root node.

Please let me know if we have a bank of such questions somewhere.

Mustafa Garhi
Ranch Hand
Posts: 111
Sri m pretty sure about my homework ..

Campbell Ritchie
Sheriff
Posts: 50251
79
You haven't solved the algorithm at all. You are spending time sorting the array, then adding to the tree, which will not give you a tree, but a linked list of some sort.

Bad luck: you will have to start again:
• Create a tree which sorts itself as you fill it
• Iterate the array and fill the tree
•
Henry Wong
author
Marshal
Posts: 21507
84
Mustafa Garhi wrote:
Algorithm :

1) Sort the array in ascending order

2) Use
fill(Node node) {

if(node.leftChild!=null) {
fill(node.leftChild);
}

node.value = sortedArr[i++];

if(node.rightChild!=null) {
fill(node.rightChild);
}

If you want more homework, how about...

1. Create the binary tree, instead of filling a binary tree -- because in real life, an "empty binary tree" means that it doesn't exist. No one encounters a problem of having a binary tree that needs filling.

2. Even harder homework, create the binary tree in a balanced manner.

3. Even harder. Do problem 2 (create balance), while you are filling it.... meaning one pass, create while transfer data from array.

4. Even harder. Do problem 3 (create balance while filling) from an unsorted array... meaning add sorting to the one pass.

Henry

Sridhar Santhanakrishnan
Ranch Hand
Posts: 317
Mustafa Garhi wrote:

Now i want more such problems because i want to test my logic.

and

Mustafa Garhi wrote:

Has anyone got any reference to such coding problems?

I think it's pretty much justified to think that you need more problems to stimulate yourself. Calling it "homework" seems to have offended you.

Mustafa Garhi
Ranch Hand
Posts: 111
Hmmm ..

Some good homework there guys.

I am not a bad guy, just learning.

Shall be patient enough now on.

Love you all