Write The Shortest Program to Calculate Height of a Binary Tree

Question

The height of a binary tree is the distance from the root node to the node child that is farthest from the root.

Below is an example:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Height of binary tree: 4

Definition of a Binary Tree

A tree is an object that contains a signed integer value and either two other trees or pointers to them.

The structure of the binary tree struct looks something like the following:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

The challenge:

Input

The root of a binary tree

Output

The number that represents the height of a binary tree

Assuming you are given the root of a binary tree as input, write the shortest program that calculates the height of a binary tree and returns the height. The program with least amount of bytes (accounting whitespaces) wins.

Answer 1

Jelly, 3 bytes

ŒḊ’

A monadic Link accepting a list representing the tree: [root_value, left_tree, right_tree], where each of left_tree and right_tree are similar structures (empty if need be), which yields the height.

Try it online!

How?

Pretty trivial in Jelly:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)

Answer 2

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 list representing the tree: [root_value, left_tree, right_tree], where each of left_tree and right_tree are similar structures (empty if need be), which returns the height.

Try it online!

^{Note that [] will return False, but in Python False==0.}

Answer 3

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: [root_value, left_tree, right_tree], where each of left_tree and right_tree are similar structures (optionally empty). I.e. [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]] represents the tree from the challenge description.

Try it online or verify a few more test cases.

Explanation:

Δ     # Loop until the (implicit) input-list no longer changes:
  €`  #  Flatten the list one level
}N    # After the loop: push the 0-based index of the loop we just finished
      # (which is output implicitly as result)

Note that although 05AB1E is 0-based, the changes-loop Δ causes the output index to be correct, because it needs an additional iteration to check it no longer changes.

Answer 4

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 equivalent of the C struct given in the challenge.

Try it online!

Answer 5

Perl 6, 25 bytes

{($_,{.[*;*]}...*eqv*)-2}

Input is a 3-element list (l, r, v). The empty tree is the empty list.

Try it online!

Explanation

{                       }  # Anonymous block
    ,        ...  # Sequence constructor
  $_  # Start with input
     {.[*;*]}  # Compute next element by flattening one level
               # Sadly *[*;*] doesn't work for some reason
                *eqv*  # Until elements doesn't change
 (                   )-2  # Size of sequence minus 2

Old solution, 30 bytes

{+$_&&1+max map &?BLOCK,.[^2]}

Try it online!

Answer 6

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

Try it online!

Commented

f =                       // f is a recursive function taking
([a, b]) =>               // a node of the tree split into
                          // a[] = left child, b[] = right child (the value is ignored)
  a ?                     // if a[] is defined:
    1 +                   //   increment the final result for this branch
    f(                    //   and add:
      f(a) > f(b) ? a : b //     f(a) if f(a) > f(b) or f(b) otherwise
    )                     //
  :                       // else:
    0                     //   stop recursion and return 0

Answer 7

C, 43 bytes

h(T*r){r=r?1+(int)fmax(h(r->l),h(r->r)):0;}

Structure of binary tree is the following:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Answer 8

JavaScript (Node.js), 32 bytes

f=a=>/,,/.test(a)&&f(a.flat())+1

Try it online!

Using the name flat instead of flatten or smoosh is a great idea for code golf.

Using [] for null node in the tree, and [left, right, value] for nodes. value here is an integer.

Answer 9

Wolfram Language (Mathematica), 10 bytes

Depth@#-2&

Try it online! Takes input as a nested list {v, l, r}.

Answer 10

Haskell, 28 bytes

Using the following data definition:

data T a = (:&) a [T a]

The height is:

h(_:&x)=foldr(max.succ.h)0 x

Answer 11

Scheme, 72 Bytes

(define(f h)(if(null? h)0(+ 1(max(f(car(cdr h)))(f(car(cdr(cdr h))))))))

More Readable Version:

(define (f h)
   (if (null? h)
      0
      (+ 1 
         (max
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))
         )
      )
   )
)

Using lists of the form (data, left, right) to represent a tree. E.g.

   1
  / \
  2  3
 /\
 4 5

is represented as: (1 (2 (4 () ()) (5 () ())) (3 () ())

(1
   (2
      (4 () ())
```   (5 () ())
   (3 () ())
)

Try it Online!

Answer 12

R, 51 bytes

function(L){while(is.list(L<-unlist(L,F)))T=T+1;+T}

Try it online!

• Input: a nested list in the format : list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

• Algorithm: Iteratively flattens the tree by one level until it becomes a flat vector : the iterations count corresponds to the max depth.

Inspired by @KevinCruijssen solution

---

Recursive alternative :

R, 64 bytes

`~`=function(L,d=0)'if'(is.list(L),max(L[[2]]~d+1,L[[3]]~d+1),d)

Try it online!

Redefines the function/operator '~' making it able to compute the max depth of a tree stored in a list structure.

The list structure of a tree is in the format : list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

• -2 thanks to @Giuseppe

Answer 13

Japt, 8 bytes

@eU=c1}a

Try it

Original, 9 bytes

Ω¡ÒßXÃrw

Try it

Answer 14

Kotlin, 45 bytes

val Tree.h:Int get()=1+maxOf(l?.h?:0,r?.h?:0)

Assuming the following class is defined

class Tree(var v: Int, var l: Tree? = null, var r: Tree? = null)

Try it online

Answer 15

K (ngn/k), 4 bytes

Solution:

#,/\

Try it online!

Explanation:

I think I may have missed the point.

Representing a tree as the 3-item list (parent-node;left-child;right-child), the example can be represented as

(2;
  (7;
    (,2);
    (6;
      (,5);
      (,11)
    )
  );
  (5;
    ();
    (9;
      (,4);
      ()
    )
  )
)

or: (2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);()))).

So the solution is to iteratively flatten, and count the iterations:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count

Answer 16

Charcoal, 29 bytes

⊞θ⁰⊞υθＦυ«≔⊕⊟ιθＦΦι∧κλ⊞υ⊞Ｏκθ»Ｉθ

Try it online! Link is to verbose version of code. Temporarily modifies the tree during processing. Explanation:

⊞θ⁰

Push zero to the root node.

⊞υθ

Push the root node to the list of all nodes.

Ｆυ«

Perform a breadth-first search of the tree.

≔⊕⊟ιθ

Get the depth of this node.

ＦΦι∧κλ

Loop over any child nodes.

⊞υ⊞Ｏκθ

Tell the child node its parent's depth and push it to the list of all nodes.

»Ｉθ

Once all the nodes have been traversed print the depth of the last node. Since the traversal was breadth-first, this will be the height of the tree.

Answer 17

Stax, 5 bytes

▐▌µ╡⌂

Run and debug it

Stax has neither pointers nor null values, so I represent the input like [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. Maybe that's an unfair advantage, but it was the closest I could get.

Unpacked, ungolfed, and commented, the code looks like this.

        The input starts on top of the input stack
Z       Tuck a zero underneath the top value in the stack.  Both values end up on the main stack.
D       Drop the first element from array
F       For each remaining element (the leaves) run the rest of the program
  G^    Recursively call the entire program, then increment
  T     Get maximum of the two numbers now ow the stack

Run this one

Answer 18

Julia, 27 bytes

f(t)=t≢()&&maximum(f,t.c)+1

With the following struct representing the binary tree:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

c is a tuple representing the left and right nodes and the empty tuple () is used to signal the absence of a node.

Answer 19

Kotlin, 42 bytes

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1

Try it online!

Where

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

Answer 20

Jq, 18 bytes

Takes input as [Value, Left, Right] or any permutation of this.

[paths|length]|max

 paths             # for each path as a list of indexes to follow
                   # to get to an element or array inside the input
                   # e.g. [0,2,1] to represent array[0][2][1]
      |length      # its length
[            ]     # collect into an array
              |max # the maximum of this array

jq play it!