Check If a Binary Tree is Balanced

Question

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 a program 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. The submission's score is the length of the code, with lower score being better.

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]

In your initial example of a tree, if you remove the leaf 4, is the remaining tree balanced? — Neil
– Neil, Commented Aug 6, 2019 at 8:43
No, not that example, I meant the initial one, using ASCII art. — Neil
– Neil, Commented Aug 6, 2019 at 23:55
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
– T. Salim, Commented Aug 7, 2019 at 0:00
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
– Geza Kerecsenyi, Commented Aug 7, 2019 at 14:59

Erik the Outgolfer · Accepted Answer · 2019-08-05 17:50:30Z

8

Jelly, 11 bytes

ḊµŒḊ€IỊ;ß€Ạ

Try it online!

The empty tree is represented by [].

answered Aug 5, 2019 at 17:50

Erik the Outgolfer

40.8k5 gold badges46 silver badges125 bronze badges

\$\begingroup\$ Thanks Erik for being amongst the first to answer this question. Jelly certainly is a very popular language on this site. I think I should take the liberty to implement this language. Good to learn from a robust golf-scripting language. \$\endgroup\$

T. Salim
– T. Salim

2019-08-05 19:14:17 +00:00
Commented Aug 5, 2019 at 19:14
\$\begingroup\$ Congrats Erik the Outgolfer, you are winner. \$\endgroup\$

T. Salim
– T. Salim

2019-08-09 01:29:19 +00:00
Commented Aug 9, 2019 at 1:29

Add a comment |

tsh · Accepted Answer · 2024-12-23 07:18:07Z

4

JavaScript (Node.js), 38 bytes

h=([l,r])=>H=l?+'112'[h(l)-h(r)+1]+H:1

Try it online!

edited Dec 23, 2024 at 7:18

answered Aug 6, 2019 at 2:51

tsh

36.2k2 gold badges36 silver badges133 bronze badges

\$\begingroup\$ You can save a byte with +h instead of NaN \$\endgroup\$

emanresu A
– emanresu A

2024-12-22 21:55:55 +00:00
Commented Dec 22, 2024 at 21:55

Add a comment |

Unrelated String · Accepted Answer · 2019-08-05 18:22:41Z

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.

(If the value of each node could be omitted from the input, _/ could be taken out for -2 bytes.) — Unrelated String
– Unrelated String, Commented Aug 6, 2019 at 3:50

alephalpha · Accepted Answer · 2019-08-06 03:44:41Z

3

Wolfram Language (Mathematica), 50 bytes

f@_[x_,y_]:=f@x&&f@y&&-2<Depth@x-Depth@y<2;f@_=1>0

Use Null for null, value[left, right] for nodes. For example, the following tree is written as 2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]].

Try it online!

edited Aug 6, 2019 at 3:44

answered Aug 6, 2019 at 3:31

alephalpha

51.9k7 gold badges75 silver badges197 bronze badges

\$\begingroup\$ That's really pretty! \$\endgroup\$

Greg Martin
– Greg Martin

2019-08-06 08:43:27 +00:00
Commented Aug 6, 2019 at 8:43

Add a comment |

ar4093 · Accepted Answer · 2019-08-06 10:01:05Z

Python 3.8 (pre-release), 133 125 bytes

b=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1)
h=lambda t:b(t)[1]

Try it online!

Takes a tree in the "list" format: A node is [value, left, right] with left and right being nodes.

Invoke the function h.

Returns 0 or False for an unbalanced tree. Returns 1 or True for a balanced tree.

Ungolfed:

# Returns tuple (current height, subtrees are balanced (or not))
def balanced(tree):
  if tree: # [] evaluates to False
    left = balanced(tree[1])
    right = balanced(tree[2])
    # If  the subtrees are not both balanced, nothing to do, just pass it up
    if left[1] and right[1]:
      height = max(left[0], right[0]) + 1
      subtrees_balanced = abs(left[0] - right[0]) < 2
    else:
      height = 0 # Value doesn't matter, will be ignored
      subtrees_balanced = False
  else:
    height = 0
    subtrees_balanced = True
  return (height, subtrees_balanced)

def h(tree):
  return balanced(tree)[1]

-10: Reversed logic to get rid of nots

If taking arguments in the middle of a call is allowed, this could be shortened to (115 bytes)

(b:=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1))(_)[1]

with _ being the tree to check.

fəˈnɛtɪk · Accepted Answer · 2019-08-05 20:00:17Z

2

JavaScript, 162 bytes

f=x=>{for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1];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])}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];){if(!((d=(t=s.pop())[0]).a&&d.b||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

edited Aug 5, 2019 at 20:00

answered Aug 5, 2019 at 18:55

fəˈnɛtɪk

4,1842 gold badges15 silver badges40 bronze badges

1

\$\begingroup\$ There is probably some way to do the breadth first search better but I couldn't think of it. \$\endgroup\$

fəˈnɛtɪk
– fəˈnɛtɪk

2019-08-05 20:01:27 +00:00
Commented Aug 5, 2019 at 20:01
1

\$\begingroup\$ I think this fails for some valid cases such as the very first example which should become balanced when you remove the leaf 4. \$\endgroup\$

Neil
– Neil

2019-08-06 08:56:03 +00:00
Commented Aug 6, 2019 at 8:56

Add a comment |

Simeon Schaub · Accepted Answer · 2019-08-06 19:47:16Z

1

Julia, 56 bytes

f(t)=t!=()&&(-(f.(t.c)...)^2<2 ? maximum(f,t.c)+1 : NaN)

With the following struct representing the binary tree:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

c is a tuple representing the left and right nodes and the empty tuple () is used to signal the absence of a node.

Falsey value is NaN, any integer is truthy.

edited Aug 6, 2019 at 19:47

answered Aug 6, 2019 at 10:39

Simeon Schaub

5512 silver badges5 bronze badges

1

\$\begingroup\$ Assuming the encoding is UTF-8, this is actually 57 bytes because of the ≢, according to TIO's built-in byte counter. Anyhow, welcome to CG&CC! \$\endgroup\$

Unrelated String
– Unrelated String

2019-08-06 19:42:55 +00:00
Commented Aug 6, 2019 at 19:42
1

\$\begingroup\$ Yes, you're right. I corrected it, so that it's now actually 56 bytes \$\endgroup\$

Simeon Schaub
– Simeon Schaub

2019-08-06 19:49:00 +00:00
Commented Aug 6, 2019 at 19:49

Add a comment |

Brojowski · Accepted Answer · 2019-08-06 05:23:29Z

0

Kotlin, 67 bytes

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1
fun N.b()=l?.c()==r?.c()

Where

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

Try it online!

answered Aug 6, 2019 at 5:23

Brojowski

1615 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

C, 117 bytes

h(T*r){r=r?1+h(h(r->l)>h(r->r)?r->l:r->r):0;}b(T*r){return r->l&&!b(r->l)||r->r&&!b(r->r)?0:abs(h(r->l)-h(r->r))<=1;}

Struct implementation is the following:

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

Try This on JDoodle

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 6, 2019 at 21:33

T. Salim

6656 silver badges15 bronze badges

\$\begingroup\$ This appears to be 117 bytes, though you can do <2 for that last check instead \$\endgroup\$

Jo King
– Jo King

2019-08-06 22:36:48 +00:00
Commented Aug 6, 2019 at 22:36
\$\begingroup\$ Also, I'm not sure how valid this is, since it relies on a data structure defined outside of the submission \$\endgroup\$

Jo King
– Jo King

2019-08-07 00:06:15 +00:00
Commented Aug 7, 2019 at 0:06

Add a comment |

Chas Brown · Accepted Answer · 2019-08-07 06:15:42Z

0

Python 2, 99 96 94 bytes

lambda A:A==[]or(abs(D(A[1])-D(A[2]))<2)*f(A[1])*f(A[2])
D=lambda A:A>[]and-~max(map(D,A[1:]))

Try it online!

3 bytes from Jo King.

Takes input as: empty node is [], and other nodes are [<value>, <leftNode>, <rightNode>]. Outputs 0/1 for False/True.

edited Aug 7, 2019 at 6:15

answered Aug 6, 2019 at 18:26

Chas Brown

9,7771 gold badge14 silver badges39 bronze badges

Add a comment |

Dannyu NDos · Accepted Answer · 2025-01-09 04:32:59Z

0

Haskell, 72 bytes

data T=L|T:!T
b L=[0]
b(l:!r)=[1+max x y|x<-b l,y<-b r,elem(y-x)[-1..1]]

Try it online!

Output format: Truthy if nonempty.

answered Jan 9 at 4:32

Dannyu NDos

7,3811 gold badge28 silver badges92 bronze badges

Add a comment |

Stack Exchange Network

Check If a Binary Tree is Balanced

11 Answers 11

Jelly, 11 bytes

JavaScript (Node.js), 38 bytes

Prolog (SWI), 49 bytes

Wolfram Language (Mathematica), 50 bytes

Python 3.8 (pre-release), 133 125 bytes

Ungolfed:

JavaScript, 162 bytes

Explanation

Julia, 56 bytes

Kotlin, 67 bytes

C, 117 bytes

Python 2, 99 96 94 bytes

Haskell, 72 bytes

Your Answer

Linked

Hot Network Questions

Check If a Binary Tree is Balanced

11 Answers 11

Jelly, 11 bytes

JavaScript (Node.js), 38 bytes

Prolog (SWI), 49 bytes

Wolfram Language (Mathematica), 50 bytes

Python 3.8 (pre-release), 133 125 bytes

Ungolfed:

JavaScript, 162 bytes

Explanation

Julia, 56 bytes

Kotlin, 67 bytes

C, 117 bytes

Python 2, 99 96 94 bytes

Haskell, 72 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions