15

2

For each node in a balanced binary tree, the maximum difference in the heights of the left child subtree and the right child subtree are at most 1.

The height of a binary tree is the distance from the root node to the node child that is farthest from the root.

Below is an example:

```
2 <-- root: Height 1
/ \
7 5 <-- Height 2
/ \ \
2 6 9 <-- Height 3
/ \ /
5 11 4 <-- Height 4
```

Height of binary tree: 4

The following are binary trees and a report on whether or not they are balanced:

The tree above is **unbalanced**.

The above tree is **balanced**.

Write the shortest program possible that accepts as input the root of a binary tree and returns a falsey value if the tree is unbalanced and a truthy value if the tree is balanced.

**Input**

The root of a binary tree. This may be in the form of a reference to the root object or even a list that is a valid representation of a binary tree.

**Output**

**Returns truthy value:** If the tree is balanced

**Returns falsey value:** If the tree is **un**balanced.

**Definition of a Binary Tree**

A tree is an object that contains a value and either two other trees or pointers to them.

The structure of the binary tree looks something like the following:

```
typedef struct T
{
struct T *l;
struct T *r;
int v;
}T;
```

If using a list representation for a binary tree, it may look something like the following:

```
[root_value, left_node, right_node]
```

2May input be empty tree? – tsh – 2019-08-06T02:43:55.827

1In your initial example of a tree, if you remove the leaf

`4`

, is the remaining tree balanced? – Neil – 2019-08-06T08:43:10.943No, not that example, I meant the initial one, using ASCII art. – Neil – 2019-08-06T23:55:26.477

According to my own implementation "C, 117 bytes": No, since the height of the right subarm tree starting from "5" is 2 and the height of the left subarm tree is 0. – T. Salim – 2019-08-07T00:00:16.120

Edits are at least 6 chars but please remove the comma from between 'balanced' and 'binary' - 'binary tree' is a noun phrase, so writing 'balanced, binary tree' is the equivalent of 'red, snow mobile' - the comma is not required. – Geza Kerecsenyi – 2019-08-07T14:59:09.713