Show off your tree analysing toolbox

Question

As a programmer or computer scientist one might encounter quite a lot of trees - of course not the woody growing-in-the-wrong-direction kind, but the nice, pure mathematical kind:

  *<- root (also a node)
 /|\<- edge
* * *<- inner node
|  / \
* *   *<- leaf (also a node)
  |
  *

Naturally over time we all have put together our own small handy toolbox to analyse such trees as we encounter them, right? Now is the time to show it off!

---

Task

The toolbox must include the following functions:

• size: The number of nodes in the tree.
• depth: The number of edges on the longest path from the root to any leaf.
• breadth: The number of leaves.
• degree: The maximum number of child nodes for any node.

You have to submit a program or function for each of the tools, however they might share subroutines (e.g. parsing) which then have to be submitted only once. Note that those subroutines need to be full programs or functions too.

---

Input Format

The trees can be given in any reasonable format capturing the structure, e.g. the tree

  *
 / \
*   *

could be represented through parentheses (()()), lists of lists [[],[]], or data structures with a constructor T[T[],T[]]. However not through linearisation [2,0,0] or a format like (size, depth, breath, degree, whatever-else-is-needed-to-make-this-format-unique-for-every-tree). Generally speaking, your tree format should not contain numbers.

Output Format

A natural number for each of the properties described above.

Scoring

Lowest code in bytes for the 4 functions in every language wins, thus I will not accept an answer.

Feel free to provide additional tree tools like fold, isBinaryTree, preLinearise, postLinearize, or whatever you like. Of course those don't have to be included in the byte count.

Examples

First the tree is given in the sample formats from above, then the results of the functions as (size, depth, breadth, degree).

()
[]
T[]
(1,0,1,0)

(()())
[[],[]]
T[T[],T[]]
(3,1,2,2)

((())()((())()))
[[[]],[],[[[]],[]]]
T[T[T[]],T[],T[T[T[]],T[]]]
(8,3,4,3)

((()())((())()((())()))(()())(()))
[[[],[]],[[[]],[],[[[]],[]]],[[],[]],[[]]]
T[T[T[],T[]],T[T[T[]],T[],T[T[T[]],T[]]],T[T[],T[]],T[T[]]]
(17,4,9,4)

((((((((()))))))))
[[[[[[[[[]]]]]]]]]
T[T[T[T[T[T[T[T[T[]]]]]]]]]
(9,8,1,1)

(((((((()()))((()()))))((((()()))((()()))))))((((((()()))((()()))))((((()()))((()())))))))
[[[[[[[[],[]]],[[[],[]]]]],[[[[[],[]]],[[[],[]]]]]]],[[[[[[[],[]]],[[[],[]]]]],[[[[[],[]]],[[[],[]]]]]]]]
T[T[T[T[T[T[T[T[],T[]]],T[T[T[],T[]]]]],T[T[T[T[T[],T[]]],T[T[T[],T[]]]]]]],T[T[T[T[T[T[T[],T[]]],T[T[T[],T[]]]]],T[T[T[T[T[],T[]]],T[T[T[],T[]]]]]]]]
(45,7,16,2)

Answer 1

Ruby, 122 110 bytes

f=->s{->t{t.to_s.scan(s).size}}
s=f[?[]
d=->t{[-1,*t.map(&d)].max+1}
b=f['[]']
g=->t{([t.size]+t.map(&g)).max}

Inspired by Neil's JavaScript solution. d and g are just translations from his JS to Ruby. For s and b I'm using string conversion tricks.

Shaved a few bytes off of s and b by adding the helper f, and a few more byte off of d and g thanks to Jordan.

Answer 2

Python, 136 bytes

f=lambda z,c:lambda t:eval(t,{'T':lambda*a:a and eval(z)or c})
s,d,b,g=map(f,['sum(a)+1','max(a)+1','sum(a)','max(len(a),*a)'],[1,0]*2)

The input format is the 'T[]' format but with parens instead of brackets and passed as a string. It's the longest submission so far, but I thought the approach is pretty cute.

Answer 3

tinylisp, 248 bytes

(d X(q((m n)(i(l m n)n m))))(d F(q(()g(c(q(T))(c(c(q i)(c(q T)g))())))))(d S(F(s(S(h T))(s 0(S(t T))))1))(d H(F(X(s 1(s 0(H(h T))))(H(t T)))0))(d B(F(s(B(h T))(s 0(i(t T)(B(t T))0)))1))(d C(F(s 1(s 0(C(t T))))0))(d D(F(X(C T)(X(D(h T))(D(t T))))0))

_{Fun fact: 49% of that program is parentheses.}

tinylisp is a minimalistic version of Lisp, containing only 10 built-in functions and macros. Because Lisp is awesome, it is nonetheless very powerful, and well-suited to manipulating abstract data structures like trees.

The program defines functions S, H (for "height"), B, and D, as well as a max function X and a number-of-children function C. It uses the (()()) form of trees, with the added requirement that each tree must be quoted to be treated as data rather than code: (q (()())). Example run:

tl> (d tree (q ((())()((())()))))
tree
tl> (S tree)
8
tl> (H tree)
3
tl> (B tree)
4
tl> (D tree)
3

Here's an ungolfed version, with a couple extra utility functions defined to make things clearer. For reference, the built-ins used are define, quote, if, less than, cons, subtract, head, and tail. (Yes, addition has to be implemented from subtraction.)

(d lambda (q (() args args)))

(d add
 (lambda (a b)
  (s a (s 0 b))))

(d max
 (lambda (a b)
  (i (l a b) b a)))

(d size
 (lambda (tree)
  (i tree
   (add (size (h tree)) (size (t tree)))
   1)))

(d depth
 (lambda (tree)
  (i tree
   (max (add 1 (depth (h tree))) (depth (t tree)))
   0)))

(d breadth
 (lambda (tree)
  (i tree
   (add
    (breadth (h tree))
    (i (t tree)
     (breadth (t tree))
     0))
   1)))

(d children
 (lambda (tree)
  (i tree
   (add 1 (children (t tree)))
   0)))

(d degree
 (lambda (tree)
  (i tree
   (max (children tree) (max (degree (h tree)) (degree (t tree))))
   0))))

This is pretty horrible Lisp style, since there's no tail recursion, but hey--it's code golf. ;^)

Answer 4

JavaScript (ES6), 131 bytes

s=a=>a.reduce((r,e)=>r+s(e),1)
d=a=>Math.max(...a.map(d),-1)+1
b=a=>a.reduce((r,e)=>r+b(e),+!a[0])
g=a=>Math.max(...a.map(g),a.length)

Since all the functions are recursive, I've given them one letter names to save bytes: size, depth, breadth and degree. Takes input using the [,] format.

Answer 5

Perl 5 - 130 bytes

sub z{$_[0]=~y/<//c}
sub d{$_=$_[0];{s/><//&&redo}-1+z$_}
sub b{()=$_[0]=~/<>/g}
sub g{(grep{$_[0]=~/<(<(?1)*>){$_}>/}0..z$_)[-1]}

These take input as a string using angle brackets (e.g. <<><>>). z (size) and b (breadth) count the substrings for either all nodes or leafs, d (depth) collapses adjacent nodes until there's no branching then gets the size, and g (degree) uses a recursive regex to test for the presence of nodes of each degree up to the size then returns the largest found.

Answer 6

C#, 380, 357 bytes

I've just noticed I forgot to remove some of my test code, so 23 bytes shaved off...

This is my first submission on PPCG and I'm not sure if the format is entirely correct especially because I'm using C#, but here are my four functions:

int d(string t){int l=-1,p=0;t.Max(m=>p=p<(l+=m=='('?1:-1)?l:p);return p;}
int s(string t){return t.Count(c=>c=='(');}
int f(string t){int q=0,w=d(t)+2;int[]l=new int[w],i=new int[w];t.Max(m=>l[q]=m=='('?l[q++]+1:(0*(i[q]=l[q]>i[q]?l[q]:i[q])*(q--)));return i.Max();}
int b(string t){var f='(';int l=0;t.Max(m=>l+=(f=='('&m==')')?(f=m)*0+1:(f=m)*0);return l;}

d: Depth s: Size: f: Degree b: Breadth

The functions use () as input

I'm using LINQ's Max function to iterate through the items in the string array. I'm not using the functionality of Max, I only use it because it's the shortest iterative function; I could just as well have used Min. There's no recursion and all is done in linear time.

A slightly more readable version of my code, but the LINQ is still a bit cryptic:

    /*Depth: Increment counter on open bracket and
     decrement on closed bracket;
     return highest number reached*/
    int d(string t)
    {
        int l = -1, p = 0;
        t.Max(m => p = p < (l += m == '(' ? 1 : -1) ? l : p);
        return p;
    }

    int s(string t)//Size: Count the number of open brackets
    {
        return t.Count(c => c == '(');
    }
    
    int f(string t)//Degree, this one took me hours to figure out
    {
        int q = 0, w = d(t) + 2;
        int[] l = new int[w], i = new int[w];
        t.Max(m => l[q] = m == '(' ? l[q++] + 1 : (0 * (i[q] = l[q] > i[q] ? l[q] : i[q]) * (q--)));
        return i.Max();
    }

    int b(string t)//Breadth
    {
        var f = '(';
        int l = 0;
        t.Max(m => l += (f == '(' & m == ')') ? (f = m) * 0 + 1 : (f = m) * 0);
        return l;
    }

Answer 7

Mathematica, 77 bytes

s=LeafCount
d=Depth@#-2&
b=Length@Level[#,{-2}]&
g=Max[Length@#,##&@@#]&//@#&

Take any Mathematica expression as input.

Answer 8

Standard ML, 149 bytes

val m=Int.max
val% =foldl
fun f?(T%)= ?(map(f?)%)
val s=f(%op+1)
val d=f(fn t=>1+ %m~1t)
val b=f(fn[]=>1|t=> %op+0t)
val g=f(fn t=>m(length t,%m 0t))

Try it on Tutorialspoint. Uses the constructor notation (e.g. T[T[],T[]]) with the following data structure declaration: datatype tree = T of tree list

Ungolfed:

fun fold f (T xs) = f (map (fold f) xs)

val size    = fold (foldl op+ 1)
val depth   = fold (fn t => 1 + foldl Int.max ~1 t)
val breadth = fold (fn nil => 1 | t => foldl op+ 0 t)
val degree  = fold (fn t => Int.max(length t, foldl Int.max 0 t))