# Binary Tree

##### Return to: Chialisp

1 / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 6 5 7 / \ / \ / \ / \ 8 12 10 14 9 13 11 15 ^ ^ ^ ^ ^ ^ ^ ^ 16-24 20-28 18-26 22-30 17-25 21-29 19-27 23-31 32-48 62 33 47-63 64-96 126 65 95-127 128 254 129 255 256 510 257 511

## Binary Tree example and explanation(as per Jakub Hadamcik 2021-07-10)

Btw there is (fairly) simple way how to calculate which # you want just by looking at solution (instead of writing very deep tree).

If you have for example `(1 2 (((5 6) 4) 3))`

and you want to know which # gets you atom for position of number 6 in that solution you just need to decode it into set of left/right (first/rest.. whatever works for you, it's same)

So you start with `1` as first and `(2 (((5 6) 4) 3))`

as rest and ask "is number I want on the left or right".. in this case it's right so you write down `R`

And you continue `2` and rest `(((5 6) 4) 3)`

=> `R`

So whole process is:

`1` and rest `(2 (((5 6) 4) 3))`

=> `R`

`2` and rest `((((5 6) 4) 3))`

=> `R`

`(((5 6) 4) 3)`

and rest `()`

=> `L`

`((5 6) 4)`

and rest `(3)`

=> `L`

`(5 6)`

and rest `(4)`

=> `L`

`5` and rest `(6)`

=> `R`

`6` and rest `nil` => `L`

so result is `RRLLLRL` this you can convert to binary where `R` => 1 and `L` = 0 so `1100010`

For each position you then need to calculate `2^position*(binary + 1)` and sum those together (sounds harder than it is 😃)

Example for `1100010`:

`1`: `2^0 * (1 + 1)` = `2`

`1`: `2^1 * (1 + 1)` = `4`

`0`: `2^2 * (0 + 1)` = `4`

`0`: `2^3 * (0 + 1)` = `8`

`0`: `2^4 * (0 + 1)` = `16`

`1`: `2^5 * (1 + 1)` = `64`

`0`: `2^6 * (0 + 1)` = `64`

and when you sum results: `2+4+4+8+16+64+64` = `162` and add 1 to it (always; because 1 is for root) so final is `163` and `brun '163' '(1 2 (((5 6) 4) 3))'`

gets you `6`

——————————————

Simpler format is in 2 rows. Top row is 2^position and bottom row is binary where if it's `L` you just take number from top row and if it's `R` you multiply it by 2. So:

1 2 4 8 16 32 64 ... 1 1 0 0 0 1 0

2 + 4 + 4 + 8 + 16 + 64 + 64 = 162