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

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]

Jelly, 11 bytes

ḊµŒḊ€IỊ;߀Ạ

Try it online!

The empty tree is represented by [].

Prolog (SWI), 49 bytes

N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.

Try it online!

Represents trees as Value/Left_Child/Right_Child, with the empty tree being the atom e. Defines +/2, which outputs through success or failure, with an unbound variable (or one already equal to the tree's height) on the left and the tree on the right--if the height argument is unacceptable, add 9 bytes to define -T:-_+T..

N + _/B/C :- % If the second argument is a tree of the form _Value/B/C,
 X+B, % X is the height of its left child which is balanced,
 Y+C, % Y is the height of its right child which is balanced,
 abs(X-Y) < 2, % the absolute difference between X and Y is strictly less than 2,
 N is max(X,Y)+1. % and N is the height of the full tree.
0 + e. % If, on the other hand, the second argument is e, the first is 0.

JavaScript, 162 bytes

f=x=>for(f=0,s=[[x,1]];s[0];)return 1

Try it online!

The format of the input is an object

root=a:node,b:node,c:value

Explanation

for(f=0,s=[[x,1]];s[0];)f))f=t[1]

Performing breadth first search find the depth of the first node which is missing one or more branches.

if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])

Continuing the breadth first search, return zero if any element is two deeper than the depth of the first node missing branches.

return 1}

If no such node is found, return 1