Meaningless Drivel is fun!*
The moose likes Beginning Java and the fly likes Empty binary tree and elements in array - Write a Program Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Empty binary tree and elements in array - Write a Program" Watch "Empty binary tree and elements in array - Write a Program" New topic
Author

Empty binary tree and elements in array - Write a Program

Mustafa Garhi
Ranch Hand

Joined: Nov 05, 2008
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.

Threads/Collections/Data Structures/Polymorphism etc preferred.

Has anyone got any reference to such coding problems?

Sony Agrawal
Ranch Hand

Joined: Oct 04, 2009
Posts: 143
What did you mean by
Mustafa Garhi wrote:read the array in one go




Mustafa Garhi
Ranch Hand

Joined: Nov 05, 2008
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

Joined: Oct 13, 2005
Posts: 39877
    
  28
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

Joined: Mar 20, 2007
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

Joined: Nov 05, 2008
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

Joined: Nov 05, 2008
Posts: 111
Sri m pretty sure about my homework ..

How about some homework for you on reading things properly ;)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39877
    
  28
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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 18997
        
      40

    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


    Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
    Sridhar Santhanakrishnan
    Ranch Hand

    Joined: Mar 20, 2007
    Posts: 317
    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

    Joined: Nov 05, 2008
    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
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Empty binary tree and elements in array - Write a Program