tvishwa107 - 6 months ago 29

Python Question

Given a height 1<=h<=15, how do I go about drawing this tree? I'll need to be able to traverse it later to solve some questions.

For h = 1, just the root labeled 1.

For h = 2,

`3`

1 2

For h = 3,

`7`

3 6

1 2 4 5

etc.

All that really strikes so far has been trying to find a relation from the top-down (for the left side tree, the left node will be (parent-1)/2 and the right child is parent-1 but this isn't a consistent pattern), but I can't seem to find anything . Since i need to be able to generate the tree, I'm not sure how to use a heap-structure either. I'm not sure where to start on recursion either. Any ideas are welcome.

Answer

Your tree could be drawn recursively, but here is non-recursive code.

```
def ruler(n):
result = 1
while not (n & 1):
n >>= 1
result += 1
return result
def printtree(h):
widthofnum = len(str(2**h - 1))
for row in range(h, 0, -1):
maxcol = 2**(h - row)
width = 2**(row-1) * (widthofnum + 1) - 1
valincr = 2**row - 2
val = valincr + 1
for col in range(1, maxcol + 1):
print(str(val).center(width), end=' ')
val += ruler(col) + valincr
print()
printtree(3)
```

That prints

```
7
3 6
1 2 4 5
```

while `printtree(5)`

gives

```
31
15 30
7 14 22 29
3 6 10 13 18 21 25 28
1 2 4 5 8 9 11 12 16 17 19 20 23 24 26 27
```

The spacing may not be ideal for larger numbers, but it works. Note that each line ends in at least one space, for code simplicity. The print statement means this is Python 3.x code. This non-recursive code lets us print from top-to-bottom, left-to-right without any backtracking or storage of strings. However, that complicates the calculations involved.

One key to that code is the discrete ruler function, which can be defined as "the exponent of the largest power of 2 which divides 2n." It is more visually seen as the height of consecutive marks on an inch ruler. This determines the increases in values between numbers in a row. The rest of the code should be straightforward.