How to create a binary decision tree in JavaScript
Tags: javascript, tutorial, computerscience, algorithms
Published: 2021-05-29 20:40:32

Stuck writing large and nested `if-else if-else` conditions? Trouble following how all these different conditions interact and flow together? Here's a tool that can help: *decision trees*.

Decision trees are a way to model conditional logic in a clear and composable way. Although commonly used in machine learning, they can be just as useful in more "typical" use cases which we will explore in this article.

This article will provide a brief introduction into trees as a data structure and decision trees as a tool, as well as their application in software development.

We will create a binary decision tree in JavaScript step-by-step and apply it to decide whether a value is a positive number, negative number, zero, or not a number at all.

Read on to find out more!

---

## What is a tree data structure?

A **tree** data structure is a type of data structure in which data - represented by **nodes** - is connected in such a way that every node **branches out** into zero or more **child nodes**.

Visualising node connections gives the structure the appearance of a tree, hence the name.

---

![An illustration of a binary tree data structure, with a red root node branching out into left and right blue child nodes; and each blue child node branching out into left and right green leaf nodes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sft3w869b8kf71r43n0e.png)

## What is a binary tree data structure?

A **binary tree** data structure is a special type of tree data structure where **every node can have up to two child nodes**: a **left child node**, and a **right child node**.

A binary tree begins with a **root node**. The root node can then branch out into left and right child nodes, each child continuing to branch out into left and right child nodes as well.

Nodes that branch out into children are called **non-leaf nodes**. Nodes without children are called **leaf nodes**.

Going through the nodes of a binary tree - **traversing** the tree - gives us the choice of moving to *either* the left or right child node - a *binary choice -* earning this type of tree the name *binary tree*.

---

## What is a decision tree?

A **decision tree** is a tool to help visualise *decisions* and the *consequences* of their *outcomes*.

At its simplest, a decision tree contains **decision nodes** and **outcome nodes** (also called *end nodes*). 

Decision trees may also contain *chance nodes*. Chance nodes serve as "weights" to favour one family of outcomes over another under certain conditions.

There are many different ways to visualise decision trees, one example being flowchart symbols.

---

![An illustration of a binary decision tree which can be used to determine if a value is less than or equal to zero, in range of 1 to 10, in range of 11 to 20, or greater than 20](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ri8sku7fofuwm93188o5.png)

## What is a binary decision tree?

A **binary decision tree** is a decision tree implemented in the form of a binary tree data structure.

A binary decision tree's *non-leaf nodes represent conditions* and its *leaf nodes represent outcomes*. 

By traversing a binary decision tree we can decide on an outcome under a given context and conditions.

---

## What are decision tree applications?

Decision trees can be applied for predictive modelling in statistics, data mining, and machine learning.

Decision trees can also be applied in game development for building AIs and branching story paths, as well as general development scenarios where there is a need to handle large chains of interconnected conditional statements.

---

## How to turn conditional statements into binary decision tree nodes?

To turn conditional statements into binary decision tree nodes, we have to treat *conditional statements* and *outcomes* as *arguments* passed to *decision functions*.

We will begin designing our decision tree data structure API by looking at conditional statements in our example.

The `decideNumberSign` function takes in a parameter `x` and attempts to return its sign, 0 or `?` if the sign cannot be determined:

```jsx
function decideNumberSign(x) {
	if (x > 0) {
		return "+";
	} else if (x < 0) {
		return "-";
	} else if (x === 0) {
		return "0";
	} else {
		return "?";
	}
}
```

When it comes to making decisions based on a condition, we need to define an outcome for the case of the condition being true, and another outcome for the case of it being false. With that in mind, our decision node function would look like this:

```jsx
decision(x > 0, "+", "-");
```

Combining decision nodes would then look like this:

```jsx
decision(x > 0, "+", decision(x < 0, "-", decision(x === 0, "0", "?")));
```

To support more complex conditions and prevent evaluating conditions on nodes that won't be traversed, we can refactor our condition expressions into functions that will only be called when the node is reached:

```jsx
const isPositive = x => x > 0;
const isNegative= x => x < 0;
const isZero = x => x === 0;

decision(isPositive, "+", decision(isNegative, "-", decision(isZero, "0", "?")));
```

With the API finalised, we can implement the function:

```jsx
const decision = (conditionFunction, trueOutcome, falseOutcome) =>
	(context) => conditionFunction(context) ? trueOutcome : falseOutcome;
```

We can now build a decision tree out of decision nodes, but we can't traverse the tree just yet. To traverse the tree and reach a decision we must be able to test the conditions by calling them with a context.

---

## How to perform binary decision tree traversal?

To traverse a binary decision tree we provide a context to the root node of the tree, which then calls its condition function and any decision node condition functions that follow as outcomes.

Let's again start by outlining the API:

```jsx
const context = "number";
const numberSignDecision = decision(isPositive, "+", decision(isNegative, "-", decision(isZero, "0", "?")));

decide(context, numberSignDecision);
```

We have to keep in mind that the outcome of our decisions - *our left and / or right child nodes* - will either be a *new decision node* (function) or *non-callable value* (anything but a function).

If the outcome of our decision is another decision node, we have to decide the new node's outcome for the current context until we reach a non-callable value.

If the outcome of our decision node is a non-callable value we return the value.

By deciding the outcome of every decision node we reach in that way, we will effectively traverse the decision tree and reach a decision.

```jsx
const decide = (context, decision) => {
	const outcome = decision(context);

	return typeof outcome === "function" ? decide(context, outcome) : outcome;
}
```

That's it, we're done! That's all there is to creating a simple binary decision tree in JavaScript.

---

## JavaScript binary decision tree example code

```jsx
// Decision tree API

const decision = (conditionFunction, trueOutcome, falseOutcome) =>
	(context) => conditionFunction(context) ? trueOutcome : falseOutcome;

const decide = (context, decision) => {
	const outcome = decision(context);

	return typeof outcome === "function" ? decide(context, outcome) : outcome;
}

// Example

const isPositive = x => x > 0;
const isNegative= x => x < 0;
const isZero = x => x === 0;

const numberSignDecision =
	decision(isPositive,
		"+",
		decision(isNegative,
			"-",
			decision(isZero,
				"0",
				"?"
			)
		)
	);

const contextValues = [ "number", 1,	0, -1, Number.NaN, ];

for (const value of contextValues) {
	console.log(value, decide(value, numberSignDecision));
}
```
{% codesandbox jr8de %}

---

## Homework and next steps

- Improve the `decision()` function to check whether the `conditionFunction` argument is a function or not before calling it. This will make the function more robust and provide us with a way to short-circuit our decision with truthy or falsey values, which can be very useful for debugging purposes.
- Try turning our binary decision tree into an m-ary decision tree. M-ary decision trees can have more than two decision nodes. In their case we may not have `true` and `false` as outcomes, but rather `1` and `0` as well as any value in between which would represent how certain we are in the outcome.

---

Thank you for taking the time to read through this article!

Do you have any experience creating decision trees? Have you tried implementing one yourself?

Leave a comment and start a discussion!