[Question]
  [
## Background
[**Fibonacci trees**](https://xlinux.nist.gov/dads/HTML/fibonacciTree.html) \$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](https://en.wikipedia.org/wiki/AVL_tree) of same height.
## Challenge
Given the number \$n\$, output the \$n\$-th Fibonacci tree.
By the usual [sequence](/questions/tagged/sequence "show questions tagged '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.
  
[Answer]
# [J](http://jsoftware.com/), 14 bytes
```
(2{.];])^:[&a:
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NYyq9WKtYzXjrKLVEq3@a3KlJmfkK6QpGEAY6rq6uuowMUMsYkZYxIyxiJn8BwA "J – Try It Online")
We use J boxes to represent the trees:
```
┌┐
││
└┘
---
┌──┬┐
│┌┐││
│││││
│└┘││
└──┴┘
---
┌─────┬──┐
│┌──┬┐│┌┐│
││┌┐││││││
│││││││└┘│
││└┘│││  │
│└──┴┘│  │
└─────┴──┘
---
┌──────────┬─────┐
│┌─────┬──┐│┌──┬┐│
││┌──┬┐│┌┐│││┌┐│││
│││┌┐│││││││││││││
││││││││└┘│││└┘│││
│││└┘│││  ││└──┴┘│
││└──┴┘│  ││     │
│└─────┴──┘│     │
└──────────┴─────┘
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 19 bytes
```
#<2||#0/@{#-1,#-2}&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7X9nGqKZG2UDfoVpZ11BHWdeoVu1/QFFmXkm0sq5dmoNyrFqdY1FRYmWd5X8A "Wolfram Language (Mathematica) – 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](https://i.stack.imgur.com/SfBu3.png)](https://i.stack.imgur.com/SfBu3.png)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 2 bytes
```
,¡
```
[Try it online!](https://tio.run/##y0rNyan8/1/n0ML//00A "Jelly – Try It Online")
**Takes input from STDIN.** Outputs the `n`th 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]
# [Haskell](https://www.haskell.org/), 34 bytes
```
data T=E|N T T
f=E:scanl N(N E E)f
```
[Try it online!](https://tio.run/##Ncs/CwIhGAbw/T7FgzR02B4Ejo655BYRL5einGeHCrf03e2taPw9fwLV2aXU@4MawSr9MrCwg1f6VCfKCWZvoKFH32OujfLkcAnPjVdbcMUNqB9pJa438QMfEsrIiZDy2yYpxeGPwuDpQjGrhdbzHWuJue0azQ5H@P4G "Haskell – 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.
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~16~~ 12 bytes
```
ΘGȯf≠'"s,s0₀
```
[Try it online!](https://tio.run/##yygtzv7//9wM9xPr0x51LlBXKtYpNnjU1PD/PwA "Husk – 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+1₀
```
[Try it online!](https://tio.run/##yygtzv7//9wMd23DR00N//8DAA "Husk – Try It Online")
This puts a 0 at the beginning of the sequence (with `Θ`), then scans (`G`) recursively the same list `₀` 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](https://codegolf.stackexchange.com/users/95126)!)*:
```
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 "
```
[Answer]
# [R](https://www.r-project.org/), 39 bytes
```
f=function(n)if(n>0)list(f(n-1),f(n-2))
```
[Try it online!](https://tio.run/##VY27CsMwDADn@CuCJwlSSEOnQPIVHQPFNRYIghxkBQIl3@4@tk533HJaiZ9ZQoz8ME1pqjTRLtE4Cwgygcw9rlwMPnq5YvfFgFgpKxwtS9uPN3y5ZlMWgy0US@DvvjsQXVNM4X8Avx6DgV/EozvrGw "R – 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]
# [Python 3](https://docs.python.org/3/), ~~53~~ ~~50~~ ~~45~~ 44 bytes
```
f=lambda n:n and[n]if n<2else[f(n-1),f(n-2)]
```
[Try it online!](https://tio.run/##FcUxCoAwDAXQq2RsQAcVl6InEYdIGw3Ub6kunr7iW15@n@PCUKvOSc4tCMGDBGHBakqY@pjuuKhD23Hz1/Na9SpkZKAi2KMb2VMuhsepM@b6AQ "Python 3 – 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.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 6 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
õ¯‚λs‚
```
Outputs the infinite sequence, with an empty string as empty node (i.e. \$T4\$ will result in `[[[[],""],[]],[[],""]]`)
[Try it online.](https://tio.run/##yy9OTMpM/f//8NZD6x81zDq3uxhI/q8tq9Q5tM3@PwA) (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]
# [JavaScript (Node.js)](https://nodejs.org), ~~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!](https://tio.run/##y0osSyxOLsosKNHNy09J/f8/zTbP1i7PxtA@OtYqOk0jT9dQUwdEGWnG/rfmijbQUTDUUTDSUTDWUTCJ1UvLL3JNTM7QyFOwtVNIzs8rzs9J1cvJT9cAatHU1PwPAA "JavaScript (Node.js) – Try It Online")
A tree is represented by `[l, r]`. The absence of a child is represented by `[]`.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 18 bytes
```
ＦＮ⊞υ✂υ±¹±³±¹∧υ⭆¹⊟υ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z8tv0hBwzOvoLTErzQ3KbVIQ1NTIaC0OEOjVEchOCczORXE8EtNTyxJ1TDUhDONNZFENTWtuQKKMvNKNBzzUsAaS4C8dN/EAg1DHYWA/AKNUk2Qov//Tf/rluUAAA "Charcoal – Try It Online") Link is to verbose version of code. Outputs nodes as arrays of between 0 and 2 elements. Explanation:
```
ＦＮ
```
Input `n` and loop `n` times.
```
⊞υ✂υ±¹±³±¹
```
Take the last and second last results (if any), and make them the children of the root of the next tree.
```
∧υ⭆¹⊟υ
```
Print the last tree, if any.
[Answer]
# [Branch](https://github.com/hyper-neutrino/branch-lang/), 35 bytes
```
/;{^\;{Z[{Z0]z^[/@^\@^0]~`L`Ln[0`P]
```
Try it on the [online Branch interpreter](https://branch.hyper-neutrino.xyz/#WyIvO3teXFw7e1pbe1owXXpeWy9AXlxcQF4wXX5gTGBMblswYFBdIiwiIiwiNCJd)!
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
```
[Answer]
# [APL(Dyalog Unicode)](https://dyalog.com), 14 bytes [SBCS](https://github.com/abrudz/SBCS)
```
{⍵>0:∇¨⍵-⍳2⋄0}
```
[Try it on APLgolf!](https://razetime.github.io/APLgolf/?h=AwA&c=q37Uu9XOwOpRR/uhFUCm7qPezUaPulsMagE&f=e9Q2Me3QCgOdR72bzQA&i=AwA&r=tryAPL&l=apl-dyalog&m=dfn&n=f)
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
```
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 34 bytes
```
K`¶
"$+"+`(.*)¶(.*)
[$1,$2]¶$1
0G`
```
[Try it online!](https://tio.run/##K0otycxLNPz/3zvh0DYuJRVtJe0EDT0tzUPbQCRXtIqhjopR7KFtKoZcBu4J//@bAgA "Retina – 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]
## 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]
# [Stax](https://github.com/tomtheisen/stax), ~~12~~ 10 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
z1]Wn|uPbs2l
```
[Run and debug it](https://staxlang.xyz/#c=z1%5DWn%7CuPbs2l&i=&a=1&m=2)
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]
# [tinylisp](https://github.com/dloscutoff/Esolangs/tree/master/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!](https://tio.run/##K8nMq8zJLC74/18jRcFNo1BDw09TI1MjR8FPwVDTQCNZw02jGMzWhLONgOz/Gm4KBppcQNIQTBqBSWMwaaL5HwA "tinylisp – 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]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 30 bytes
```
f(n)=if(n>0,[f(n-1),f(n-2)],0)
```
[Try it online!](https://tio.run/##K0gsytRNL/j/P00jT9M2E0jaGehEAyldQ00dEGWkGatjoPk/saAgp1IjT0HXTqGgKDOvBMhUAnGUFEAaNXWiDfT0DA1iNf8DAA "Pari/GP – Try It Online")
[Answer]
# [Kotlin](https://kotlinlang.org), ~~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!](https://tio.run/##y84vycnM@/8/rTRPIU0jz8ozr0TTyjGv0rY8IzVPI0@z2kDXTslAicsQSEUbxipxpeYUp4LYKtVA5bqGmrU6EJaRZm2sUi3YnNzEzDwNTYVqLgUgSMsvUtBQyFTIzFMw1NMzVYCJg0BBUWZeSU6eRppGpqYmWLSWq/Y/AA "Kotlin – Try It Online")
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 19 bytes
```
L?b?qb1]b,ytbyttbby
```
[Try it online!](https://tio.run/##K6gsyfj/38c@yb4wyTA2SaeyJKmypCQpqfL/f1MA "Pyth – Try It Online")
---
Near literal translation of n1k9's Python 3 answer.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~214~~ 175 bytes
-39 bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/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!](https://tio.run/##dVLLbsIwELz7K9wgJLu229gthWIoP9FbyCE4oRjVmyqEXqJ8e@oEwkOUPXi1s7O7M5KN@DKmGVgw3/s0w7Ndmdr8afPRmE1SYBdJFUejMNaGAK3WBPiDy9wuK4njL4q/hSHl8AhU123P8i2tXGTjaBvPXycahFyAUAsPMelBAc/KN8a8B1gHvCvup4XklinuSbQr1aFkQKfERYz5rUJsj@MX5YROQ103v7lN8U9hofwssozgrqYaIY9gl1ggFFcI@@iedV6QtpPgOZbapxke@8RYzzox2zAk8atu4O7cmgTtRTwYpktYQsDvUztlx2591lJk5b4AHGpUI/S/D1TdqA4PqqW8L7unrw70laeP2nxNvxq5tDU0AfdfIImjVXzhqT6b2pc7EgQnR3XzBw "C (gcc) – 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.
]