Jump to content
  • Advertisement
Sign in to follow this  
Nicholas Kong

How to find left child and right child using an array implementation

This topic is 1843 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I took my second exam in Data Structures. There was a question that I could not understand. I recall it was worth 2 points so it should have been straightforward.

 

It say something similar like: If a binary tree was implemented using an array implementation. In Java A[0] retrieves the first element in the array. How do I retrieve the left and right child?

 

I did not want to leave the question blank so I wrote A[0.leftchild] and A[0.rightchild].  

Share this post


Link to post
Share on other sites
Advertisement

The question is about how you would implement a binary tree, using a regular 1D array as the storage area for the nodes.

 

For example, given an array of 7 nodes, you could define the left/right child relationships between the nodes like in this image:

GbIhk6j.png

e.g. the root node is at 0, it's left child is at 1 and right child at 4. The node at 1 has it's left child at 2 and right child at 3. The node at 4 has it's left child at 5 and right child at 6. The nodes at 2/3/5/6 are leaf nodes.

 

The examiner wanted you to write out a formula that would take a node index as input (and probably also the tree depth/array size as an input too), and produce the left/right node indices as output.

Share this post


Link to post
Share on other sites

The question is about how you would implement a binary tree, using a regular 1D array as the storage area for the nodes.

 

For example, given an array of 7 nodes, you could define the left/right child relationships between the nodes like in this image:

GbIhk6j.png

e.g. the root node is at 0, it's left child is at 1 and right child at 4. The node at 1 has it's left child at 2 and right child at 3. The node at 4 has it's left child at 5 and right child at 6. The nodes at 2/3/5/6 are leaf nodes.

 

The examiner wanted you to write out a formula that would take a node index as input (and probably also the tree depth/array size as an input too), and produce the left/right node indices as output.

Why is the left child is at 1 and the right child is at 4 given a root node at 0? Why not make the left child at 1 and right child at 4? Would there be an issue? The left and right child are far apart in the array given a node at 0. But at node 1 and node 4 the children are close together in the array.

Share this post


Link to post
Share on other sites

Alvaro has the right answer. I assume it is supposed to be a heap structure, since that is expandable (to as many nodes deep as you wish) in a straightforward manner.

 

Hodgman's method requires moving nodes if an extra level in the tree hierarchy is added.

Share this post


Link to post
Share on other sites

Why is the left child is at 1 and the right child is at 4 given a root node at 0? Why not make the left child at 1 and right child at 4? Would there be an issue? The left and right child are far apart in the array given a node at 0. But at node 1 and node 4 the children are close together in the array.

The picture was just an example of mapping the nodes of the tree to different array indices. I deliberately didn't post a real formula so you could still learn it by yourself wink.png

 

Álvaro's post contains the links that you should read.

Share this post


Link to post
Share on other sites

Why is the left child is at 1 and the right child is at 4 given a root node at 0? Why not make the left child at 1 and right child at 4? Would there be an issue? The left and right child are far apart in the array given a node at 0. But at node 1 and node 4 the children are close together in the array.

The picture was just an example of mapping the nodes of the tree to different array indices. I deliberately didn't post a real formula so you could still learn it by yourself wink.png

 

Álvaro's post contains the links that you should read.

Ah I see so there is multiple solutions to this then. Thanks for not posting a real formula!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!