Binary Tree

In Ruby

In a really cool talk yesterday at a coding Meetup event the speaker made a reference to a term that sounded quite like something I studied in math, but that I hadn’t heard of before in my semi-newish studies of programming- a Binary Tree. Fearing this was a gaping hole of knowledge (especially when he mentioned the term so casually, as if everyone who codes should definitely know what a Binary Tree is) I immediately texted my math-know-it-all-friend and did some hard googling to find answers.

A Binary Tree, it turns out, is a pretty straight forward concept (and incidentally is quite common both in computer science and in mathematics). The best way to understand a binary tree is to look at a picture:

A binary tree is a data structure (hashes and arrays are both other types of data structures commonly used in programming). A binary tree consists of nodes linked together by an ‘edge’. There is a root node which is the topmost node in the tree (the 10 in the picture above), and each node can have at most 2 children called the left child/node and right child/node respectively. Nodes with no children are called leaves or external nodes, whereas nodes that are not leaves are called internal nodes. Nodes with the same parent are called siblings.

*Depth of a node is the number of edges from the root to the node
*Height of a node is the number of edges from the node to the deepest leaf
*Height of a tree is the height of the root
*a Full Binary Tree is one where each node has exactly zero or two children
*a Complete Binary Tree is one that is completely filled with the possible exception of the bottom level- and is filled from left to right
*Traversal: this is a process that visits all the nodes in the tree

In programming, binary trees are commonly used for storing sorted data and for quickly retrieving that stored data. Nodes/leaves on the left have a lower/lesser key value and the leaf on the right has an equal or larger key value. So, if you look at the binary tree picture above that is numbered, you can see that the lowest/most left node has the lowest number/key value. As you can see, this binary tree is a fractal and that means it is easier to manipulate, because you can use recursion to call on consecutive nodes/leaves to access and insert data.


Apparently, Ruby’s library has arrays and hashes but not binary trees. However, it isn’t too difficult to build your own binary tree in Ruby (bc its a superior coding language and the one with which I’m most familiar).

The cool thing about the binary tree data structure is that you can use Enumerable methods on them (if you include it in your class) just like with arrays and hashes. There are tons of resources on the web if binary trees and their uses interest you:

Much more impressive Ruby binary tree code: ** a gem!!!

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.