Fibonacci trees

Question

Background

Fibonacci trees \$T_n\$ are a sequence of rooted binary trees of height \$n-1\$. They are defined as follows:

• \$T_0\$ has no nodes.
• \$T_1\$ has a single node (the root).
• The root node of \$T_{n+2}\$ has \$T_{n+1}\$ as its left subtree and \$T_n\$ as its right subtree.

T0 T1 T2 T3 T4
 O O O O
 / / \ / \
 O O O O O
 / / \ /
 O O O O
 /
 O

Each tree in this sequence is the most unbalanced possible state of an AVL tree of same height.

Challenge

Given the number \$n\$, output the \$n\$-th Fibonacci tree.

By the usual sequence rules, your function or program may behave as one of the following:

• Take \$n\$ as input, and output the \$n\$-th tree (\$n\$ can be 0- or 1-indexed; the given example is 0-based)
• Take \$n\$ as input, and output the first \$n\$ trees
• Take no input, and output the sequence of trees indefinitely

A binary tree can be output in any acceptable ways, including but not limited to

• a built-in tree object if your language has one,
• a nested array, an ADT, or its textual representation,
• a human-readable ASCII/Unicode art, or
• a flattened list of nodes labeled as numbers in level order.

Shortest code in bytes wins.

• Hood: This is irrelevant to the challenge, but I think T_0 is technically not a tree but only a forest. In my opinion a tree should have exactly one connected component. However, T_0 does satisfy the definition of tree given on wikipedia: "for every pair of vertices there is a unique path between them". This is vacuously satisfied by the empty graph.
• Bubbler: @Hood True, and actually my definition of Fibonacci trees doesn't work for T0 because a tree height of -1 doesn't make much sense. It merely serves as a base case to correctly define T2 and beyond.
• Wheat Wizard: In the nested array representation is an empty array, an empty tree or a node with no children? And either way how is the opposite one represented? (I ask because in my experience usually the nested array representation is taken to represent rooted trees, which do not include the empty tree).
• Bubbler: @WheatWizard Honestly I didn't think of consequences of the empty graph. But for example, you can represent the empty graph as [], and then the single-node graph becomes [[],[]]. Or you can wrap the entire graph in an Option type, etc.

Answer 1

J, 14 bytes

(2{.];])^:[&a:

Try it online!

We use J boxes to represent the trees:

┌┐
││
└┘
---
┌──┬┐
│┌┐││
│││││
│└┘││
└──┴┘
---
┌─────┬──┐
│┌──┬┐│┌┐│
││┌┐││││││
│││││││└┘│
││└┘│││ │
│└──┴┘│ │
└─────┴──┘
---
┌──────────┬─────┐
│┌─────┬──┐│┌──┬┐│
││┌──┬┐│┌┐│││┌┐│││
│││┌┐│││││││││││││
││││││││└┘│││└┘│││
│││└┘│││ ││└──┴┘│
││└──┴┘│ ││ │
│└─────┴──┘│ │
└──────────┴─────┘

• Eric Duminil: I'm flabbergasted

Answer 2

Wolfram Language (Mathematica), 19 bytes

#<2||#0/@{#-1,#-2}&

Try it online!

1-indexed. Returns the \$n\$th tree.

Expressions in Mathematica are trees. True represents the absence of a node.

Visually:

f[5]//TreeForm

Answer 3

Jelly, 2 bytes

,¡

Try it online!

Takes input from STDIN. Outputs the nth Fibonacci tree in the form of a nested list, where a list represents a node and 0 represents NIL.

Explanation

• , — Pair
• ¡ — Turn the preceding dyadic function f(x, y) into a triadic function g(x, n, y) such that:
  • g(x, 0, y) = x
  • g(x, 1, y) = f(x, y)
  • g(x, n, y) = f(g(x, n-1, y), g(x, n-2, y))

Since the link is called as a nilad, zeros are supplied for x and y and a number from STDIN is taken for n.

Answer 4

Haskell, 34 bytes

data T=E|N T T
f=E:scanl N(N E E)f

Try it online!

f is the infinite list of Fibonacci trees, represented as a custom type defined in the first line (E is the empty tree, N l r is the tree with left subtree l and right subtree r).

How?

Haskell is usually very well-suited for Fibonacci-related tasks. Assume we have a recurrence of the form $$ \begin{cases} \texttt{f}_0=\texttt{a}\\ \texttt{f}_1=\texttt{b}\\ \texttt{f}_{n+2}=\texttt{g}(\texttt{f}_{n+1},\texttt{f}_n), \end{cases} $$ where \$\texttt{g}\$ is a binary operator. Then the corresponding Haskell definition is simply

f=a:scanl g b f

Unfortunately, Haskell is not very well-suited for problems involving trees, since it can't (natively) handle nested lists or tuples. Defining my own data type for trees was the shortest way I could find to solve this issue.

• Bubbler: I guess you had to solve this because you initially posted an answer to a wrong challenge :P Nice to see a custom datatype in a golfed answer though.
• Delfad0r: @Bubbler Woops ^^. That's why you never work on two problems at the same time.

Answer 5

Husk, (削除) 16 (削除ここまで) 12 bytes

ΘGȯf≠'"s,s00

Try it online!

Trees or arbitrarily nested lists are not a thing in Husk, so this builds a string representation of the tree, where a leaf is represented as "0" and a node with a Left child L and a right child R is represented as "(L,R)".

Returns the infinite list of Fibonacci trees, which get printed one per line.

Explanation

I've started from what's probably the second shortest way of computing Fibonacci numbers in Husk (the shortest being the builtin İf):

ΘG+10

Try it online!

This puts a 0 at the beginning of the sequence (with Θ), then scans (G) recursively the same list 0 with +, starting from 1 and summing every time the last result to the next element in the list.

With this, we just need to alter the starting values and the + operator to make it compute Fibonacci trees.

The 1 now becomes "0" (s0, string representation of the number 0) and the 0 turns into "" automagically, thanks to Husk understanding that the list is now a list of strings rather than numbers. The operator that generates a new tree from the two previous ones becomes a bit more complex (but not as complex as I originally made it, thanks Dominic van Essen!):

f≠'"s, Input: left subtree "L", right subtree "R"
 , Join the two subtrees in a pair ("L","R")
 s Convert the pair into a string "(\"L\",\"R\")"
Now we need to remove the extra quotes:
f Keep only those characters
 ≠ that are different
 '" than "

• Dominic van Essen: 14 bytes by exploiting the fact that Husk pairs already look like (,)...
• Dominic van Essen: ...and then 13 bytes by representing nodes as x instead of ()...
• Leo: @DominicvanEssen and using 0 instead saves another byte! Thank you, that was a very smart way to do it :)

Answer 6

R, 39 bytes

f=function(n)if(n>0)list(f(n-1),f(n-2))

Try it online!

Output is a nested list of lists of 2 elements each.
Leaves are represented as lists with no child lists (both list elements are NULL).

Answer 7

Python 3, (削除) 53 (削除ここまで) (削除) 50 (削除ここまで) (削除) 45 (削除ここまで) 44 bytes

f=lambda n:n and[n]if n<2else[f(n-1),f(n-2)]

Try it online!

Thanks @Dominic van Essen save 3 bytes.

Save 5 bytes changing the first if condition with and.

Thanks @user save 1 byte.

• Dominic van Essen: Nice one. Defining a node as [1] is readable, but if you instead define a node as [0, 0] (in other words, a tree with no branches) then you can save 16 bytes...
• Dominic van Essen: (or 50 bytes without changing the node definition)...
• n1k9: @Dominic van Essen Nice
• user: Looks like you missed a space after [n].
• movatica: 43 bytes

Answer 8

05AB1E, 6 bytes

õ ̄‚λs‚

Outputs the infinite sequence, with an empty string as empty node (i.e. \$T4\$ will result in [[[[],""],[]],[[],""]])

Try it online. (The footer is to print each tree on a separated line with newline-delimiters. Feel free to remove it to see the actual infinite list output.)

Explanation:

 λ # Start a recursive environment
 # to output the infinite sequence,
õ # starting at a(0)=""
 ̄‚ # and a(1)=[]
õ ̄‚ # (Push an empty string ""; push an empty list []; pair them together)
 # And we calculate every following a(n) as follows:
 # (implicitly push the values of a(n-2) and a(n-1)
 s # Swap them on the stack
 ‚ # And pair them together: [a(n-1),a(n-2)]

Answer 9

JavaScript (Node.js), (削除) 29 (削除ここまで) 27 bytes

Saved 2 bytes with a suggestion from Jo King.

f=n=>n<1?[]:[f(n-1),f(n-2)]

Try it online!

A tree is represented by [l, r]. The absence of a child is represented by [].

Answer 10

Charcoal, 18 bytes

FN⊞υ✂υ±1±3±1∧υ⭆1⊟υ

Try it online! Link is to verbose version of code. Outputs nodes as arrays of between 0 and 2 elements. Explanation:

FN

Input n and loop n times.

⊞υ✂υ±1±3±1

Take the last and second last results (if any), and make them the children of the root of the next tree.

∧υ⭆1⊟υ

Print the last tree, if any.

Answer 11

Branch, 35 bytes

/;{^\;{Z[{Z0]z^[/@^\@^0]~`L`Ln[0`P]

Try it on the online Branch interpreter!

Of course, it's only natural that a language based on binary trees would have a way to solve this challenge. Branch is still in development; I'm not sure how I could've solved this before adding a bunch of bugfixes and a couple of new helpers.

Pretty-printing the tree was actually around from the start though. I used it as a debug feature; never thought I would've found a challenge so soon to use a debug feature as output formatting for :P

Explanation

The command line argument is automatically loaded into the first and only node in the binary tree. Note that [...] is the same as in BF; that is, it's a while loop, so if the current value is 0 at [, it skips to ], and if the current value is non-zero at ], it jumps back to [. Therefore, [...0] will only run if the value is non-zero, but then the value is zeroed at the end and so it never runs more than once. Essentially, this is an if statement.

/;{ Go to the left child, copy the parent, and decrement
^\;{ Go back to the parent, go to the right child, copy, and decrement
Z Save the value to register Z
[ 0] If that value is not zero
 {Z Decrement and save to Z (we need to save the value because it gets zeroed to allow the if statement to end)
z Restore Z; this is (parent value - 2) if parent value is not 1, and otherwise just 0
^ Go back to the parent
[ 0] If the node is non-zero
 /@ Go to the left child and run this line on that, returning here when done
 ^\@ Go to the right sibling and run this line on that, returning here when done
 ^ Go to the parent, then zero it to end the if statement
~ Return to @, if we are currently in a sub-evaluation. If not, this gets skipped, and we can end the program
`L Delete all leaves; every node with leaves is a 0 with -1 and -2 as children; these shouldn't be output
`L Delete all leaves again; it might be valid to output such that these leaves are considered the "null" elements like my APL solution and the 2-byte jelly solution do, but I decided to remove them for style and this code is long enough as it is
[ ] While this node is non-zero (input 0 and 1 give the same tree, so we need to suppress output if the value was 0)
 0 Zero the top node; this turns the while loop into an if statement and also prevents the final output from having the value there
 `P Pretty-print the tree; this was created for debugging purposes, but conveniently enough, lets us answer this challenge quite nicely

• hyperneutrino: @DLosc oh, I accidentally deleted it off my server lol. It should work now

Answer 12

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}14 bytes ^SBCS

{⍵>0:∇ ̈⍵-⍳2⋄0}

Try it on APLgolf!

Outputs as a nested list, where each list contains two elements which are the left and right children, and 0 is null.

-10 bytes thanks to Razetime and user, and also using a better online interface courtesy of Razetime

Explanation

{ } dfn
 ⍵>0: if the argument is greater than 0
 ∇ ̈ - recurse; apply this dfn to each of
 ⍵- - the argument minus (vectorizes)
 ⍳2 - [1, 2]
 ⋄0 else, just return 0

• Razetime: You can submit tryAPL solutions on APLgolf: 16 bytes
• user: 14 bytes?: {⍵>0:∇¨⍵-⍳2⋄0}. I can't get {×⍵:∇¨⍵-⍳2⋄0} to work, though
• hyperneutrino: @user Oh that's clever. I'll take a look at trying to golf it a bit more from there too; thanks.
• hyperneutrino: @Razetime that's a very nice site. Thanks!

Answer 13

Retina, 34 bytes

K`¶
"$+"+`(.*)¶(.*)
[1,ドル2ドル]¶1ドル
0G`

Try it online! Outputs a tree of tuples. No test suite due to the program's use of history. Explanation:

K`¶

Replace the input with a newline, representing two empty trees.

"$+"+`

Repeat the number of times given by the original input...

(.*)¶(.*)
[1,ドル2ドル]¶1ドル

... create a node containing the previous two trees, and forget the second last tree.

0G`

Keep only the last tree.

Answer 14

Common Lisp, 58 bytes

(defun f(n)(case n(0())(1 0)(t(cons(f(1- n))(f(- n 2))))))

Example:

USER> (loop for i from 0 to 7 do (print (f i)))
NIL 
0 
(0) 
((0) . 0) 
(((0) . 0) 0) 
((((0) . 0) 0) (0) . 0) 
(((((0) . 0) 0) (0) . 0) ((0) . 0) 0) 
((((((0) . 0) 0) (0) . 0) ((0) . 0) 0) (((0) . 0) 0) (0) . 0) 

Additionally, if you (ql:quickload :memoize), you can do (memoize-function 'f) and it will cache intermediate results.

Answer 15

Stax, ^{(削除) 12 (削除ここまで)} 10 bytes

z1]Wn|uPbs2l

Run and debug it

A bit long since the trees need to be printed as a string to be observed.

Explanation

z1]Wn|uPbs2l
z1] push empty list and [1] (base cases)
 W loop forever
 n copy the second to last element
 |u uneval (JSON.Stringify)
 P pop & print with newline
 b copy top two elements
 s swap
 2l two element list 
 

Answer 16

tinylisp, (削除) 46 (削除ここまで) 45 bytes

(d F(q((N)(i(l N 1)0(c(F(s N 1))(c(F(s N 2))(

Try it online!

A function submission that takes an integer and returns a list:

• The empty tree is represented by 0
• A nonempty tree is represented by a two-element list containing its left and right subtrees

Ungolfed

Recursively implements the definition: if N is less than 1, returns 0; otherwise, constructs a list containing the results of two recursive calls, one for N-1 and one for N-2.

(load library)
(def F
 (lambda (N)
 (if (less? N 1)
 0
 (cons
 (F (- N 1))
 (cons
 (F (- N 2))
 ())))))

Answer 17

Pari/GP, 30 bytes

f(n)=if(n>0,[f(n-1),f(n-2)],0)

Try it online!

Answer 18

Kotlin, (削除) 85 (削除ここまで) 71 bytes

Thanks to @user, saved 14 bytes

fun f(n:Int):Any=when(n){0->"0"
1->"[1]"
else->"[${f(n-1)},${f(n-2)}]"}

Try it online!

• user: Welcome to Code Golf and Coding Challenges Stack Exchange, and nice answer! You can get 71 bytes

Answer 19

Pyth, 19 bytes

L?b?qb1]b,ytbyttbby

Try it online!

---

Near literal translation of n1k9's Python 3 answer.

Answer 20

C (gcc), (削除) 214 (削除ここまで) 175 bytes

-39 bytes thanks to ceilingcat

char m[12][50];c(n){f(n,!memset(m,32,600),n*n);}f(n,i,j){m[i][j]=48;n-1?n-2?m[i+1][j-n/2]=47,m[i+1][j+n/2]=92,f(n-1,i+2,j-n),f(n-2,i+2,j+n):(m[++i][--j]=47,m[++i][--j]=48):0;}

Try it online!

I chose the ASCII art for fun.
The code consists of a function c() whose role is to call f(), just once. f() is a very creative recursive function with a passion for drawing trees on blank arrays.

Only the first 5 trees are correct. To display bigger trees I should use an exponential law for the spacing between the nodes, but if I do so, then the highest nodes would be so distant from each other that you wouldn't recognize bigger trees anyway.

I will post a conceptually right solution.

• Bubbler: Definitely interesting, but the convention here is that submissions should theoretically work for higher inputs (I know this is debatable). My suggestion is to actually apply exponential spacing so that at least it doesn't conceptually break.
• anotherOne: @Bubbler All right I will modify it.
• anotherOne: @Bubbler I am coding from the phone an if instead of j-n and j+n I put j-n*n and j+n*n (correcting also the position of slashes and backslashes, the starting column of the root and the size of the array) I can only see till tree #4, cause the width of #5 doesn't fit in the screen and character go on a new line. I don't know if doing n*n would be enough, maybe is already too much or maybe not. I guess that putting j-pow(n,n) would be safe and doesn't conceptually break, but my trees would become an abstraction that nobody could see.
• Bubbler: You can always include two versions of code: one for theoretically working (therefore valid for the challenge), and another for human-observable/whatever interesting stuff (this doesn't need to be valid for the challenge).
• anotherOne: Ahaha all right I will add a valid code