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

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

## 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 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:

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 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:

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 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 on other sites

In a binary tree, the left and right child of an index are 2n+1 and 2n+2.

##### 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

##### 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

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

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013556
×