Binary Tree array iteration

Question

I have this output, I just need to understood, how they used those indexes to represent a binary tree?

How many numbers?: 6

Enter 1st number: 50
Enter 2nd number: 60
Enter 3rd number: 40
Enter 4th number: 15
Enter 5th number: 30
Enter 6th number: 27

BST Array:
[0]     50
[1]     40
[2]     60
[3]     15
[8]     30
[17]    27

It starts from 0,1,2,3 then suddenly turn to index 8 then 17 (All other indexes are empty I guess, but why index 8 then 17?).

Is there a question there somewhere? You need to provide some extra context. — pcalcao
– pcalcao, Commented Apr 16, 2012 at 13:29
I don't think it's clear what 1st number, 2nd number, etc means. I assume these are numbers you are adding to the binary tree but the ordering or the intended space on the tree are not clear. Storing a binary tree in an array is a very common idea and should come up quickly after a little searching. If you have a particular question about it, maybe you can rephrase? — jeff
– jeff, Commented Apr 16, 2012 at 13:38
Most of the answer depends on the exact type of binary tree, the mapping is probably bitwise but that's only a guess. — biziclop
– biziclop, Commented Apr 16, 2012 at 13:41

b.buchhold · Accepted Answer · 2012-04-16 14:05:01Z

2

This seems to be a plain binary tree without balancing. I guess it's something like this:

root -> index 0

left of root/index 0 -> index 1

right of root/index 0 -> index 2

left of index 1 -> index 3

right of index 1 -> index 4

left of index 2 -> index 5

right of index 2 -> index 6

left of index 3 -> index 7

right of index 3 -> index 8

left of index 4 -> index 9

right of index 4 -> index 10

...

left of index i -> 2*i + 1

right of index i -> 2*i + 2

On the example:

For example, 15 is located at index 3. 30 is its right child and hence will be at index 2*3 + 2 = 8. 27 is the left child of the element at index 8 and hence located at index 2 * 8 + 1 = 17.

edited Apr 16, 2012 at 14:05

answered Apr 16, 2012 at 13:57

b.buchhold

3,9062 gold badges29 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jürgen Paul Over a year ago

btw: what kind of traversal is this?

b.buchhold Over a year ago

It's no traversal. It's just the simple insertion algorithm: search for the element you want to insert and if there nothing to continue, insert it there. You start at the root and for every node you go left if the element in question is smaller than the element at that node and right if it is larger.

Collectives™ on Stack Overflow

Binary Tree array iteration

1 Answer 1

On the example:

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

On the example:

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related