Binary Tree

Christopher Diep
2 min readNov 20, 2018

Get ready for the wild recursion ride.

Photo by Cameron Kirby on Unsplash

What is a Binary Tree?

Let’s start by talking about the data structure known as a tree. (I touched on this briefly with tries/prefix trees but let’s review.)

A tree has nodes (or data elements) with pointers to other nodes.

Image source: https://en.wikipedia.org/wiki/Binary_tree

Tree terms

Parent: A node is a parent node if it points to other nodes.

Children: A node is a child of a node that points to it.

Descendant: If there is path from a node and its child (or its child’s child… or it’s child’s child’s child… or so on), then it is considered a descendant. (e.g. 2,6, 5, and 11 are descendents of 7.)

Ancestor: If a node is a descendent of another node, that “another node” is called an ancestor.

Root: The biggest baddest ancestor node (e.g. 2)

Leaves: The leaves are nodes without any children. The end of the line…

I most commonly encounter tree data structures when it comes to the file system on my computer or the DOM when developing a website. When do you see trees?

Binary Tree

//JavaScript implementationclass BinaryTree {
constructor(x = null, l = null, r = null) {
this.x = x;
this.l = l;
this.r = r;
}
}

In binary trees, each node has at most 2 children. From the JavaScript implementation above, a node without any children would have the left or right point to null.

It’s the simplest to discuss given the time constraints of an interview; however, your mileage may vary.

An easy question from HackerRank

So the height of a binary tree is determined by counting the nodes starting at the root (which is height 0) to the furthest leaf.

Here’s a JavaScript implementation of a function that would get the height:

//JavaScript implementationfunction getHeight(tree) {
if (tree === null || tree.x === null) return -1;

return 1 + Math.max(getHeight(tree.l), getHeight(tree.r))
}

The recursion is strong in this one. It looks quite elegant for traversing down into the depths of this tree.

Sources

--

--