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