Write The Shortest Program to Calculate Height of a Binary Tree



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:


The root of a binary tree


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.

T. Salim

Posted 2019-08-04T17:28:21.440

Reputation: 575

4What do languages without pointers take? – Jonathan Allan – 2019-08-04T17:37:39.053

Good question, they take a reference to the instance of the tree object. I think I might want to provide the implementation of a tree object in that case. – T. Salim – 2019-08-04T17:38:25.767

4...but then my tree object could just have a property, say h. Might be better to define a specific structure made just of lists for the purpose of this challenge. – Jonathan Allan – 2019-08-04T17:40:35.043


@T.Salim In the future, please consider posting in the sandbox first.

– wizzwizz4 – 2019-08-04T17:44:38.467

Sure wizzwizz4. Will do. – T. Salim – 2019-08-04T17:45:34.847

1So, is a valid representation a list of length 3 [root_value, left_node, right_node] where each of left_node and right_node are also binary trees acceptable? It'll be trivial in many languages, but might be fun in some others. – Jonathan Allan – 2019-08-04T17:50:59.973

As long as it works as a valid binary tree structure, sure. – T. Salim – 2019-08-04T17:51:31.950

3Can you edit the question to include what constitutes a valid binary structure? Perhaps a definition like a tree is an object that contains a value and either two other trees or pointers to them. A definition that is inclusive of languages without objects would also be nice too. – Jo King – 2019-08-04T21:54:43.400

Yes, I have added a Definition of Binary Tree section. – T. Salim – 2019-08-04T21:56:28.507

Can we exclude the value part of the tree, since it has no bearing on the challenge itself? – Jo King – 2019-08-04T22:15:08.083

If not, what values can the value be? The struct has only integers, but can they also be strings or trees themselves? – Jo King – 2019-08-04T22:23:05.277

I specified that each node must store a signed integer value. – T. Salim – 2019-08-04T22:26:07.073

Can you please add some more test cases? – Shaggy – 2019-08-05T11:55:49.413



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!


Pretty trivial in Jelly:

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

Jonathan Allan

Posted 2019-08-04T17:28:21.440

Reputation: 67 804

Jonathon Allen, that is an interesting language you are using. As a newcomer, may you provide a link or a website referral that tutors people how to use Jelly? – T. Salim – 2019-08-04T17:53:49.357


Click the link in the header - it's a golfing Language developed by Dennis, one of the site's moderators.

– Jonathan Allan – 2019-08-04T17:56:12.360

2I wonder how controversial it would be to represent a leaf as x instead of [x, [], []]... – Erik the Outgolfer – 2019-08-04T18:19:26.857

@EriktheOutgolfer To keep with the "pointer" and "struct" nature of the question I think every node should be of the same form. – Jonathan Allan – 2019-08-04T18:28:44.553


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.

Jonathan Allan

Posted 2019-08-04T17:28:21.440

Reputation: 67 804

The same person is allowed to give two different answers to the same question? – T. Salim – 2019-08-04T18:36:35.440

6Yeah, of course, golf is a competition at a language level. Even a second entry in the same language is sometimes acceptable, if the approach is very different. – Jonathan Allan – 2019-08-04T18:39:39.210

@Arnauld Guess so (I'd assumed non-integers might be present for some reason) – Jonathan Allan – 2019-08-04T18:46:23.797


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!


Posted 2019-08-04T17:28:21.440

Reputation: 34 639


Perl 6, 25 bytes


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

Try it online!


{                       }  # 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!


Posted 2019-08-04T17:28:21.440

Reputation: 10 037

The &?BLOCK trick is interesting but it's a couple of bytes shorter to assign the block to $!

– Jo King – 2019-08-04T21:49:45.307

@JoKing I don't know. Storing the challenge solution in a volatile global like $! or $/ feels like cheating to me. – nwellnhof – 2019-08-04T21:56:49.773

(Ab)using variables like $! and $/ is fairly standard practice for golfing P6. – user0721090601 – 2019-08-06T04:47:18.337


05AB1E, 11 7 5 bytes


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


Δ     # 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.

Kevin Cruijssen

Posted 2019-08-04T17:28:21.440

Reputation: 67 575

17 bytes? – Expired Data – 2019-08-05T10:01:46.850

@ExpiredData Ah, of course.. Thanks! :) – Kevin Cruijssen – 2019-08-05T10:04:30.833

15 bytes – Grimmy – 2019-08-19T13:05:48.393

@Grimy I thought using the index outside a loop only worked in the legacy code.. :S Thanks! – Kevin Cruijssen – 2019-08-19T13:10:21.270


JavaScript (ES6),  35  33 bytes

Input structure: [[left_node], [right_node], value]


Try it online!


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


Posted 2019-08-04T17:28:21.440

Reputation: 111 334

Looks like you can save a byte with a&&-~. – Shaggy – 2019-08-04T23:03:58.797


@Shaggy That would lead to comparisons with undefined.

– Arnauld – 2019-08-04T23:12:24.557


C, 43 bytes


Structure of binary tree is the following:

typedef struct tree
  struct tree * l;

  struct tree * r;

  int v;

} tree;

T. Salim

Posted 2019-08-04T17:28:21.440

Reputation: 575


55 bytes Try it online! Some C-specific golfing tricks are here!

– ErikF – 2019-08-04T20:41:48.693


@ErikF Or 45 bytes

– Arnauld – 2019-08-04T20:46:03.377

Thanks ErikF and Arnauld. I should try out the ternary operator more often instead of if-else-if chains. – T. Salim – 2019-08-04T20:49:37.880

243 bytes – nwellnhof – 2019-08-04T21:36:38.373

3If your submission relies on flags, can you please add them to the header of your submission? – Jo King – 2019-08-04T22:20:49.427


Building on @nwellnhof 42 bytes

– ceilingcat – 2019-09-27T18:05:17.023


JavaScript (Node.js), 32 bytes


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.


Posted 2019-08-04T17:28:21.440

Reputation: 13 072


Wolfram Language (Mathematica), 10 bytes


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


Posted 2019-08-04T17:28:21.440

Reputation: 15 731

If 2[7[2,6[5,11]],5[9[4,],]] is a valid representation of the tree, Depth works – attinat – 2019-08-15T23:50:26.507


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

Michael Klein

Posted 2019-08-04T17:28:21.440

Reputation: 2 111


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)
      (+ 1 
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))

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

  / \
  2  3
 4 5

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

      (4 () ())
```   (5 () ())
   (3 () ())

Try it Online!

Zachary Cotton

Posted 2019-08-04T17:28:21.440

Reputation: 679


R, 51 bytes


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


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


Posted 2019-08-04T17:28:21.440

Reputation: 4 599

why do you use d=1 and then d-1 at the end? Couldn't you start at 0? – Giuseppe – 2019-08-05T16:34:31.920

Also I switched > to ~ here so the test cases are easier to input

– Giuseppe – 2019-08-05T16:34:48.853

@Giuseppe: of course...I was missing the obvious ‍♂️ – digEmAll – 2019-08-05T20:48:43.550


Japt, 8 bytes


Try it

Original, 9 bytes


Try it


Posted 2019-08-04T17:28:21.440

Reputation: 24 623


K (ngn/k), 4 bytes



Try it online!


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


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


Posted 2019-08-04T17:28:21.440

Reputation: 3 635


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.


Posted 2019-08-04T17:28:21.440

Reputation: 95 035


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


Posted 2019-08-04T17:28:21.440

Reputation: 8 616


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

Aso Leo

Posted 2019-08-04T17:28:21.440

Reputation: 101


Julia, 27 bytes


With the following struct representing the binary tree:

struct Tree

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


Posted 2019-08-04T17:28:21.440

Reputation: 381


Kotlin, 42 bytes

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

Try it online!


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


Posted 2019-08-04T17:28:21.440

Reputation: 141