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.