# Binary Tree

*Get ready for the wild recursion ride.*

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

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

…