Calculating depth of binary tree in ruby

04/05/2023

I recently was given a problem that touched on an area of computer science that I have virtually no experience of: binary trees and their related algorithms.

The problem is to compute the depth of a binary tree represented by a flat array, e.g [1, 2, 3, -1, 3, 4, -1, -1, -1]. This example would produce a binary tree looking like the below, with a depth of 4. I create a tree like so, encoding it as JSON only so I can pipe it to jq to quickly visualise it:

Note that the "traversal" of this binary tree is "pre-order". "Traversal" refers to the algorithm by which nodes are visited. A traversal, of which there are different kinds, provides a systematic way to explore a tree.