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