4
\$\begingroup\$

Given an integer \$n > 1\$, output a balanced binary tree with \$n\$ leaf nodes.

The tree should be constructed out of (space), \ and / (slashes). Each slash represents a branch.

  • A node is represented by adjacent slashes: /\. There must be a root node at the top of the tree (i.e. the first row of the output).
  • To construct the next row of the output, take each slash in the previous row at position \$i\$. You can do one of the following:
    • Terminate the branch: put a space. That branch now ends in a leaf.
    • Extend the branch: put a slash in the same direction as the slash above (i.e. if there's a \ in column \$i\$ above, put a \ in column \$i+1\$; if there's a / in column \$i\$ above, put a / in column \$i-1\$.
    • Create another branch: put an internal node (/\) at the appropriate location below the slash above.
  • You cannot have different branches converge - i.e. no \/.

Since this is a balanced binary tree, at each branching off point, the height of the left and right subtrees cannot differ by more than one. In other words, you must fill up level \$l\$ with leaves/branches before putting leaves/branches in level \$l+1\$.

Examples

A balanced binary tree with \$2\$ nodes could look like:

/\

or

 /\
/  \

but not, for example,

 /\
 \/
 /\

If \$n=3\$, you could have

  /\
 /\ \

or

  /\
 / /\
/ /  \

If \$n=4\$, you could have

  /\
 /  \
/\  /\

but not

 /\
/\/\

or

/\
  \
  /\
 /\

Standard loopholes apply, shortest code wins.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Charcoal, 47 bytes

Nθ≔L↨⊖θ²ηFηF⌊⟦X²ι⁻θX²ι⟧«≔X²⁻⊖ηιζJ×ζ⊕×⁴κ±⊖ζ↗ζ↓↘ζ

Try it online! Link is to verbose version of code. Explanation:

Nθ≔L↨⊖θ²ηFη

Input n and loop up until the ceiling of its logarithm to base 2. (This represents the "height" of the tree.)

F⌊⟦X²ι⁻θX²ι⟧«

Loop over the branches in pairs. (For the last row, the number of branches might be less than a power of 2, so that the final number of leaves is n.)

≔X²⁻⊖ηιζJ×ζ⊕×⁴κ±⊖ζ↗ζ↓↘ζ

Draw each pair of branches. Bottom branches are 1 character tall while each higher branch is extended to be twice as tall in total as the previous.

If trailing blank lines are allowed then the last can be removed. (Alternatively, I'm hoping to fix the Charcoal bug that generates those blank lines, but there are so many edge cases that it will take some time to work through them all.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.