18
votes
Fibonacci trees
J, 14 bytes
(2{.];])^:[&a:
Try it online!
We use J boxes to represent the trees:
...
- 34.1k
16
votes
Rows of the Collatz tree
K (ngn/k), 37 35 bytes
{x#x(,/{(4=6!x*4<x)(-6!)\2*x}')\,1}
Try it online!
How it works
"n is even and (n-1)/3 is an ...
- 79.3k
14
votes
Accepted
Find a fraction's parent in the Stern-Brocot tree
JavaScript (ES11), 46 bytes
-2 thanks to @Shaggy
-2 thanks to @tsh
Expects (n,d) as BigInts and returns [n',d'].
...
- 206k
13
votes
Is this a BST pre-order traversal?
JavaScript (Node.js), 49 bytes
a=>!a.some((p,i)=>a.some((q,j)=>q>p&a[j+=j>i]<p))
Try it online!
Using the fact that for array \$a_0 ... a_{...
- 36.2k
13
votes
Count unrooted, unlabeled binary trees of n nodes
JavaScript (ES6), 265 bytes
This code actually builds all possible trees and filters out isomorphic results. This is quite slow for \$n>9\$ but \$a(10)=18\$ was checked locally.
...
- 206k
13
votes
Ranking of binary trees
Jelly, 8 4 bytes
BÞŒ¿
Try it online!
-4 because WHY exactly did I think Hamming weight was involved again??
Returns the rank 1-indexed, but the test harness ...
- 23.9k
11
votes
Accepted
Write The Shortest Program to Calculate Height of a Binary Tree
Jelly, 3 bytes
ŒḊ’
A monadic Link accepting a list representing the tree: [root_value, left_tree, right_tree], where each of <...
- 115k
11
votes
Accepted
Decide Contiguous Binary Tree
Jelly, 11 10 9 8 7 bytes
ŒṪ’UḄṬP
Try it online!
-1 thanks to Jonathan Allan--funny that I used ŒṪ earlier, but never tried ...
- 23.9k
10
votes
Write The Shortest Program to Calculate Height of a Binary Tree
Python 2, 35 33 bytes
Thanks to Arnauld for noicing an oversight and saving 4.
f=lambda a:a>[]and-~max(map(f,a))
A recursive function accepting a ...
- 115k
9
votes
Is this a BST pre-order traversal?
Jelly, 7 bytes
ŒPŒ¿€4ḟ
Try it online!
Returns [4] for traversals, otherwise [].
...
- 69.7k
9
votes
Fibonacci 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. ...
- 22.8k
8
votes
Binary tree rotations
Haskell, 93 92 84 83 82 bytes
data B=B[B]Int|L
k!B[l@(B[x,y]a),r]n|k<n=B[k!l,r]n|k>n=B[l,k!r]n|1>0=B[x,B[y,r]k]a
Thanks to @BMO, @alephalpha and @Laikoni ...
- 5,017
8
votes
Accepted
Check If a Binary Tree is Balanced
Jelly, 11 bytes
ḊµŒḊ€IỊ;߀Ạ
Try it online!
The empty tree is represented by [].
- 40.8k
8
votes
Fibonacci trees
Jelly, 2 bytes
,¡
Try it online!
Takes input from STDIN. Outputs the nth Fibonacci tree in the form of a nested list, where a ...
- 8,293
7
votes
Write The Shortest Program to Calculate Height of a Binary Tree
05AB1E, 11 7 5 bytes
Δ€`}N
-4 bytes thanks to @ExpiredData.
-2 bytes thanks to @Grimy.
Input format is similar as the Jelly answer: a list representing the tree: <...
- 136k
7
votes
Count unrooted, unlabeled binary trees of n nodes
JavaScript (ES6), 267 bytes
A slightly longer but much faster version that implements the formula described in A000672, which itself is based on A001190.
...
- 206k
7
votes
Create Word Lightning
Charcoal, 88 bytes
↓§θ⁰⊞υ⁺Ｅ³¦⁰θＦυ«≔¬§ι⁰ηＦΦι›λ³«≔§κ⁰ζ≔§Φζ№§ι³λ⁰εＪ§ι¹§ι²Ｍ⌕§ι³ε✳⁻⁶§ι⁰Ｍ⌕ζε✳⁻²η⊞υ⁺⟦ηⅈⅉ⟧κ✳⁻⁶ηζ≦±η
Try it online! Link is to verbose version of code. ...
- 184k
7
votes
Ranking of binary trees
Python, 115 bytes
lambda n:[*permutations(range(n))].index((t:=lambda x:x<n and(x,)+t(2*x+1)+t(2*x+2)or())(0))
from itertools import*
Attempt This Online!
...
- 13.7k
6
votes
Binary tree rotations
Vim, 25 bytes
Takes the input in the buffer - space separated key and tree. The tree is expected to be represented as follows:
leaf: []
node with key ...
- 17k
6
votes
Write The Shortest Program to Calculate Height of a Binary Tree
Haskell, 33 bytes
h L=0
h(N l r _)=1+max(h l)(h r)
Using the custom tree type data T = L | N T T Int, which is the Haskell ...
- 36k
6
votes
Write The Shortest Program to Calculate Height of a Binary Tree
Perl 6, 25 bytes
{($_,{.[*;*]}...*eqv*)-2}
Input is a 3-element list (l, r, v). The empty tree is the empty list.
Try it ...
- 10.6k
6
votes
Fibonacci trees
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 ...
- 6,276
6
votes
Rows of the Collatz tree
Jelly, 23 bytes
ḤḤ,’÷3ƊƊḂ?€FḞƑƇ>Ƈ1
1ÇС
Try It Online!
I doubt this is optimal; I kind of ended up patching together like three fixes in a row on my original ...
- 42.8k
6
votes
Increasing permutation trees
Python NumPy, 72 bytes
lambda n:(mat(tril(cumsum(r_[1:n+3]),1),"O")**n)[0,0]
from numpy import*
Attempt This Online!
Same as below but as a function (no outer loop):
Python NumPy, 85 bytes
...
- 6,034
6
votes
Increasing permutation trees
Python 3.8 (pre-release), 85 80 bytes
def f(n,s=1,*a):
for _ in"__"*~-n:a=s,*[s:=s+x for x in a[::-1]]
print(s>>~-n)
Try it online! Link ...
- 184k
6
votes
Decide Contiguous Binary Tree
Wolfram Language (Mathematica), 55 bytes
-6 bytes thanks to @att.
Length[l=If[0>##,0,#+2#0@##2]&@@@#~Position~_List]l&
Try it online!
- 51.9k
6
votes
Number of complete binary unordered tree-factorizations of n
Haskell, 49 bytes
f n=max 1$sum[f a*f b|a<-[2..n],b<-[2..a],a*b==n]
Try it online!
- 150k
5
votes
Write The Shortest Program to Calculate Height of a Binary Tree
JavaScript (ES6), 35 33 bytes
Input structure: [[left_node], [right_node], value]
f=([a,b])=>a?1+f(f(a)>f(b)?a:b):0
...
- 206k
5
votes
5
votes
Is this a BST pre-order traversal?
Ruby, 46 40 38 bytes
f=->r{a,*b=r;!a||b==b&[*0..a]|b&&f[b]}
Try it online!
This works by recursively taking the first element ...
- 23.4k
Only top scored, non community-wiki answers of a minimum length are eligible