Given an integer \$n > 1\$, output a balanced binary tree with \$n\$ leaf nodes.
The tree should be constructed out of
/ (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\$.
A balanced binary tree with \$2\$ nodes could look like:
/\ / \
but not, for example,
/\ \/ /\
If \$n=3\$, you could have
/\ /\ \
/\ / /\ / / \
If \$n=4\$, you could have
/\ / \ /\ /\
/\ \ /\ /\
Standard loopholes apply, shortest code wins.