Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Empty binary tree and elements in array - Write a Program

 
Mustafa Garhi
Ranch Hand
Posts: 111
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Threads/Collections/Data Structures/Polymorphism etc preferred.

Has anyone got any reference to such coding problems?

 
Sony Agrawal
Ranch Hand
Posts: 143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What did you mean by
Mustafa Garhi wrote:read the array in one go




 
Mustafa Garhi
Ranch Hand
Posts: 111
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 48910
58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sri m pretty sure about my homework ..

How about some homework for you on reading things properly ;)
 
Campbell Ritchie
Sheriff
Posts: 48910
58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
    Pie
    Posts: 21114
    78
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Mustafa Garhi wrote:

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


    and

    Mustafa Garhi wrote:
    Threads/Collections/Data Structures/Polymorphism etc preferred.

    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hmmm ..

    Some good homework there guys.

    I am not a bad guy, just learning.

    Shall be patient enough now on.

    Love you all
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic