Array-list implementation of tree problem

[s3a]

Homework Statement

a) Draw a single binary tree that gave the following traversals:
Inorder: T N C K V A S M W Q B R L
Postorder: T C N V S A W M B Q L R K

b) Assume that the binary tree from the above part (a) of this question is stored in an array-list as a complete binary tree as discussed in class. Specify the contents of such an array-list for this tree.

Homework Equations

If the first element's index starts at pos=1, the index of the left child of a certain element is 2*pos, and the index of the right child of a certain element is 2*pos+1.

The Attempt at a Solution

Here is the tree sought by part a.:
...K
.../\
..N...R
../\.../\
T..C...Q..L
.../\
...M..B
.../\
...A..W
.../\
..V..S

I am trying to do part b.

If I (incorrectly) assume that the above tree is a complete tree (like it seems that the question wants me to do), I get stuck when implementing the tree into an array(list), as can be seen below. (Sorry about the formatting.):

Indices: 0 1 2 3 4 5 6 7 8 9 10 11 12
Elements in the same order as the indices above: K N R T C Q L ? ? ? ? M B

What am I doing wrong?

Any input would be GREATLY appreciated!

 

[Mark44]

Does this wiki article help? https://en.wikipedia.org/wiki/Tree_traversal
They discuss depth-first searches - pre-order, in-order, and post-order, as well as breadth-first searches.

 

[s3a]

Does this wiki article help? https://en.wikipedia.org/wiki/Tree_traversal
They discuss depth-first searches - pre-order, in-order, and post-order, as well as breadth-first searches.

I do understand part a.

As for part b, I'm not 100% sure. Is it the case that the array-list would have a lot of cells with no values filled in as shown in my array-list representation below (unlike a tree that were complete, whose array-list representation would have indices 0 to 12, where each cell would contain an element)?:
Index | Element Contained
0 | K
1 | N
2 | R
3 | T
4 | C
5 | Q
6 | L
7 | empty
8 | empty
9 | empty
10 | empty
11 | M
12 | B
13 | empty
14 | empty
15 | empty
16 | empty
17 | empty
18 | empty
19 | empty
20 | empty
21 | empty
22 | empty
23 | A
24 | W
25 | empty
26 | empty
27 | empty
28 | empty
29 | empty
30 | empty
31 | empty
32 | empty
33 | empty
34 | empty
35 | empty
36 | empty
37 | empty
38 | empty
39 | empty
40 | empty
41 | empty
42 | empty
43 | empty
44 | empty
45 | empty
46 | empty
47 | V
48 | S

 

[Mark44]

Your binary tree has 6 levels, with 13 entries, so a complete binary tree with this many levels would have at most 63 entries (1 at the root at level 0, 2 at the level 1, 4 at level 2, and so on down to 32 at level 5). 1 + 2 + 4 + 8 + 16 + 32 = 63.

Based on what you wrote in Relevant Equations, K should be at index 1 in the array. K's left child N should be at index 2*1 = 2, and the right child R should be at index 2*1 + 1 = 3. Treating N as the root of a subtree, its left child T should be stored at index 2*2 = 4, and the right child C stored at index 2*(3) + 1 = 7. Continue the indexing with the subtree headed by R until you all of the tree entries are indexed.

If you do this in C or other C-based languages, array indexes start at 0, so all the numbers I wrote are too large by 1, and can be adjusted accordingly. Inasmuch as your tree isn't complete, there will be a 63 - 13 = 50 entries in the array that are empty.