J, 14 bytes

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

Try it online!

We use J boxes to represent the trees:

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

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:

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.

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.

Husk, 16 12 bytes

ΘGȯf≠'"s,s0₀ 

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!

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!):

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 " 

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).

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.

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)] 

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 [].

Charcoal, 18 bytes

ＦＮ⊞υ✂υ±¹±³±¹∧υ⭆¹⊟υ 

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.

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 

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 

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.

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.

Stax, ¹² 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 

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)) ()))))) 

Pari/GP, 30 bytes

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

Try it online!

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!

Pyth, 19 bytes

L?b?qb1]b,ytbyttbby 

Try it online!

Near literal translation of n1k9's Python 3 answer.

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.