Write The Shortest Program To Check If A Binary Tree Is BalancedWrite The Shortest Program to Calculate Height of a Binary TreeConvert binary search tree into ordered linked listTree traversingAre these trees isomorphic?Pre-order + post-order to in-orderIs it a Linearized Tree? (Breadth-first Edition)Compute the height of a radix treeRooting for Trees With the Right NodesBinary tree rotationsIs this a BST pre-order traversal?Write The Shortest Program to Calculate Height of a Binary Tree
Build a mob of suspiciously happy lenny faces ( ͡° ͜ʖ ͡°)
What is the opposite of "hunger level"?
Can anybody tell me who this Pokemon is?
What would cause a nuclear power plant to break down after 2000 years, but not sooner?
Unsolved Problems due to Lack of Computational Power
Why do we use low resistance cables to minimize power losses?
Problem with GFCI at start of circuit with both lights and two receptacles
Are there any rules on how characters go from 0th to 1st level in a class?
Do predators tend to have vertical slit pupils versus horizontal for prey animals?
Gofer work in exchange for LoR
What's the relationship betweeen MS-DOS and XENIX?
Units of measurement, especially length, when body parts vary in size among races
Regression when x and y each have uncertainties
Interaction between Leonin Warleader and Divine Visitation
Are there any OR challenges that are similar to kaggle's competitions?
What if a restaurant suddenly cannot accept credit cards, and the customer has no cash?
Parse a simple key=value config file in C
Is this "Faetouched" homebrew race balanced?
How to prevent criminal gangs from making/buying guns?
If I am sleeping clutching on to something, how easy is it to steal that item?
programming a recursive formula into Mathematica and find the nth position in the sequence
Did Michelle Obama have a staff of 23; and Melania have a staff of 4?
Are unaudited server logs admissible in a court of law?
Difference between "va faire" and "ira faire"
Write The Shortest Program To Check If A Binary Tree Is Balanced
Write The Shortest Program to Calculate Height of a Binary TreeConvert binary search tree into ordered linked listTree traversingAre these trees isomorphic?Pre-order + post-order to in-orderIs it a Linearized Tree? (Breadth-first Edition)Compute the height of a radix treeRooting for Trees With the Right NodesBinary tree rotationsIs this a BST pre-order traversal?Write The Shortest Program to Calculate Height of a Binary Tree
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
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]
code-golf decision-problem binary-tree tree-traversal
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
add a comment |
$begingroup$
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]
code-golf decision-problem binary-tree tree-traversal
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
2
$begingroup$
May input be empty tree?
$endgroup$
– tsh
Aug 6 at 2:43
1
$begingroup$
In your initial example of a tree, if you remove the leaf4, is the remaining tree balanced?
$endgroup$
– Neil
Aug 6 at 8:43
$begingroup$
No, not that example, I meant the initial one, using ASCII art.
$endgroup$
– Neil
Aug 6 at 23:55
$begingroup$
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.
$endgroup$
– T. Salim
Aug 7 at 0:00
$begingroup$
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.
$endgroup$
– Geza Kerecsenyi
Aug 7 at 14:59
add a comment |
$begingroup$
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]
code-golf decision-problem binary-tree tree-traversal
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
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]
code-golf decision-problem binary-tree tree-traversal
code-golf decision-problem binary-tree tree-traversal
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
edited Aug 7 at 15:28
T. Salim
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
asked Aug 5 at 17:14
T. SalimT. Salim
3522 silver badges14 bronze badges
3522 silver badges14 bronze badges
2
$begingroup$
May input be empty tree?
$endgroup$
– tsh
Aug 6 at 2:43
1
$begingroup$
In your initial example of a tree, if you remove the leaf4, is the remaining tree balanced?
$endgroup$
– Neil
Aug 6 at 8:43
$begingroup$
No, not that example, I meant the initial one, using ASCII art.
$endgroup$
– Neil
Aug 6 at 23:55
$begingroup$
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.
$endgroup$
– T. Salim
Aug 7 at 0:00
$begingroup$
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.
$endgroup$
– Geza Kerecsenyi
Aug 7 at 14:59
add a comment |
2
$begingroup$
May input be empty tree?
$endgroup$
– tsh
Aug 6 at 2:43
1
$begingroup$
In your initial example of a tree, if you remove the leaf4, is the remaining tree balanced?
$endgroup$
– Neil
Aug 6 at 8:43
$begingroup$
No, not that example, I meant the initial one, using ASCII art.
$endgroup$
– Neil
Aug 6 at 23:55
$begingroup$
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.
$endgroup$
– T. Salim
Aug 7 at 0:00
$begingroup$
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.
$endgroup$
– Geza Kerecsenyi
Aug 7 at 14:59
2
2
$begingroup$
May input be empty tree?
$endgroup$
– tsh
Aug 6 at 2:43
$begingroup$
May input be empty tree?
$endgroup$
– tsh
Aug 6 at 2:43
1
1
$begingroup$
In your initial example of a tree, if you remove the leaf
4, is the remaining tree balanced?$endgroup$
– Neil
Aug 6 at 8:43
$begingroup$
In your initial example of a tree, if you remove the leaf
4, is the remaining tree balanced?$endgroup$
– Neil
Aug 6 at 8:43
$begingroup$
No, not that example, I meant the initial one, using ASCII art.
$endgroup$
– Neil
Aug 6 at 23:55
$begingroup$
No, not that example, I meant the initial one, using ASCII art.
$endgroup$
– Neil
Aug 6 at 23:55
$begingroup$
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.
$endgroup$
– T. Salim
Aug 7 at 0:00
$begingroup$
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.
$endgroup$
– T. Salim
Aug 7 at 0:00
$begingroup$
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.
$endgroup$
– Geza Kerecsenyi
Aug 7 at 14:59
$begingroup$
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.
$endgroup$
– Geza Kerecsenyi
Aug 7 at 14:59
add a comment |
10 Answers
10
active
oldest
votes
$begingroup$
Jelly, 11 bytes
ḊµŒḊ€IỊ;߀Ạ
Try it online!
The empty tree is represented by [].
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
$endgroup$
$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
Aug 5 at 19:14
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
add a comment |
$begingroup$
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.
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
$endgroup$
$begingroup$
(If the value of each node could be omitted from the input,_/could be taken out for -2 bytes.)
$endgroup$
– Unrelated String
Aug 6 at 3:50
add a comment |
$begingroup$
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]]].
2
/
7 5
/
2 6 9
/ /
5 11 4
Try it online!
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
$endgroup$
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
add a comment |
$begingroup$
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.
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 49 bytes
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1
Try it online!
-9 bytes by Arnauld.
JavaScript, 58 bytes
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1
Try it online!
Use [] for null, and [left, right, value] for nodes.
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
$endgroup$
add a comment |
$begingroup$
JavaScript, 162 bytes
f=x=>for(f=0,s=[[x,1]];s[0];)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];)
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
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
$endgroup$
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
Aug 5 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 leaf4.
$endgroup$
– Neil
Aug 6 at 8:56
add a comment |
$begingroup$
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::NTuple2,UnionTree,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.
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
$endgroup$
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
Aug 6 at 19:42
1
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
add a comment |
$begingroup$
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 at 5:23
BrojowskiBrojowski
615 bronze badges
$endgroup$
add a comment |
$begingroup$
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)
Struct implementation is the following:
typedef struct T
struct T * l;
struct T * r;
int v;
T;
Try This on JDoodle
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
$begingroup$
This appears to be 117 bytes, though you can do<2for that last check instead
$endgroup$
– Jo King
Aug 6 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
Aug 7 at 0:06
add a comment |
$begingroup$
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.
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f189285%2fwrite-the-shortest-program-to-check-if-a-binary-tree-is-balanced%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Jelly, 11 bytes
ḊµŒḊ€IỊ;߀Ạ
Try it online!
The empty tree is represented by [].
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
$endgroup$
$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
Aug 5 at 19:14
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
add a comment |
$begingroup$
Jelly, 11 bytes
ḊµŒḊ€IỊ;߀Ạ
Try it online!
The empty tree is represented by [].
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
$endgroup$
$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
Aug 5 at 19:14
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
add a comment |
$begingroup$
Jelly, 11 bytes
ḊµŒḊ€IỊ;߀Ạ
Try it online!
The empty tree is represented by [].
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
$endgroup$
Jelly, 11 bytes
ḊµŒḊ€IỊ;߀Ạ
Try it online!
The empty tree is represented by [].
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
answered Aug 5 at 17:50
Erik the OutgolferErik the Outgolfer
35.6k4 gold badges30 silver badges111 bronze badges
35.6k4 gold badges30 silver badges111 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
Aug 5 at 19:14
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
add a comment |
$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
Aug 5 at 19:14
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
$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
Aug 5 at 19:14
$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
Aug 5 at 19:14
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
$begingroup$
Congrats Erik the Outgolfer, you are winner.
$endgroup$
– T. Salim
Aug 9 at 1:29
add a comment |
$begingroup$
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.
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
$endgroup$
$begingroup$
(If the value of each node could be omitted from the input,_/could be taken out for -2 bytes.)
$endgroup$
– Unrelated String
Aug 6 at 3:50
add a comment |
$begingroup$
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.
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
$endgroup$
$begingroup$
(If the value of each node could be omitted from the input,_/could be taken out for -2 bytes.)
$endgroup$
– Unrelated String
Aug 6 at 3:50
add a comment |
$begingroup$
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.
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
$endgroup$
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.
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
answered Aug 5 at 18:22
Unrelated StringUnrelated String
3,3152 gold badges3 silver badges17 bronze badges
3,3152 gold badges3 silver badges17 bronze badges
$begingroup$
(If the value of each node could be omitted from the input,_/could be taken out for -2 bytes.)
$endgroup$
– Unrelated String
Aug 6 at 3:50
add a comment |
$begingroup$
(If the value of each node could be omitted from the input,_/could be taken out for -2 bytes.)
$endgroup$
– Unrelated String
Aug 6 at 3:50
$begingroup$
(If the value of each node could be omitted from the input,
_/ could be taken out for -2 bytes.)$endgroup$
– Unrelated String
Aug 6 at 3:50
$begingroup$
(If the value of each node could be omitted from the input,
_/ could be taken out for -2 bytes.)$endgroup$
– Unrelated String
Aug 6 at 3:50
add a comment |
$begingroup$
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]]].
2
/
7 5
/
2 6 9
/ /
5 11 4
Try it online!
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
$endgroup$
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
add a comment |
$begingroup$
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]]].
2
/
7 5
/
2 6 9
/ /
5 11 4
Try it online!
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
$endgroup$
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
add a comment |
$begingroup$
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]]].
2
/
7 5
/
2 6 9
/ /
5 11 4
Try it online!
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
$endgroup$
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]]].
2
/
7 5
/
2 6 9
/ /
5 11 4
Try it online!
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
edited Aug 6 at 3:44
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
answered Aug 6 at 3:31
alephalphaalephalpha
22.7k3 gold badges31 silver badges98 bronze badges
22.7k3 gold badges31 silver badges98 bronze badges
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
add a comment |
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
$begingroup$
That's really pretty!
$endgroup$
– Greg Martin
Aug 6 at 8:43
add a comment |
$begingroup$
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.
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
$endgroup$
add a comment |
$begingroup$
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.
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
$endgroup$
add a comment |
$begingroup$
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.
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
$endgroup$
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.
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
edited Aug 6 at 10:01
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
answered Aug 6 at 8:51
ar4093ar4093
1414 bronze badges
1414 bronze badges
add a comment |
add a comment |
$begingroup$
JavaScript (Node.js), 49 bytes
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1
Try it online!
-9 bytes by Arnauld.
JavaScript, 58 bytes
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1
Try it online!
Use [] for null, and [left, right, value] for nodes.
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 49 bytes
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1
Try it online!
-9 bytes by Arnauld.
JavaScript, 58 bytes
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1
Try it online!
Use [] for null, and [left, right, value] for nodes.
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 49 bytes
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1
Try it online!
-9 bytes by Arnauld.
JavaScript, 58 bytes
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1
Try it online!
Use [] for null, and [left, right, value] for nodes.
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
$endgroup$
JavaScript (Node.js), 49 bytes
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1
Try it online!
-9 bytes by Arnauld.
JavaScript, 58 bytes
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1
Try it online!
Use [] for null, and [left, right, value] for nodes.
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
edited Aug 7 at 2:25
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
answered Aug 6 at 2:51
tshtsh
11.3k1 gold badge17 silver badges59 bronze badges
11.3k1 gold badge17 silver badges59 bronze badges
add a comment |
add a comment |
$begingroup$
JavaScript, 162 bytes
f=x=>for(f=0,s=[[x,1]];s[0];)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];)
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
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
$endgroup$
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
Aug 5 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 leaf4.
$endgroup$
– Neil
Aug 6 at 8:56
add a comment |
$begingroup$
JavaScript, 162 bytes
f=x=>for(f=0,s=[[x,1]];s[0];)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];)
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
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
$endgroup$
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
Aug 5 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 leaf4.
$endgroup$
– Neil
Aug 6 at 8:56
add a comment |
$begingroup$
JavaScript, 162 bytes
f=x=>for(f=0,s=[[x,1]];s[0];)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];)
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
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
$endgroup$
JavaScript, 162 bytes
f=x=>for(f=0,s=[[x,1]];s[0];)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];)
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
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
edited Aug 5 at 20:00
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
answered Aug 5 at 18:55
fəˈnɛtɪkfəˈnɛtɪk
3,7562 gold badges6 silver badges37 bronze badges
3,7562 gold badges6 silver badges37 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
Aug 5 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 leaf4.
$endgroup$
– Neil
Aug 6 at 8:56
add a comment |
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
Aug 5 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 leaf4.
$endgroup$
– Neil
Aug 6 at 8:56
1
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
Aug 5 at 20:01
$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
Aug 5 at 20:01
1
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
Aug 6 at 8:56
$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
Aug 6 at 8:56
add a comment |
$begingroup$
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::NTuple2,UnionTree,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.
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
$endgroup$
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
Aug 6 at 19:42
1
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
add a comment |
$begingroup$
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::NTuple2,UnionTree,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.
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
$endgroup$
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
Aug 6 at 19:42
1
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
add a comment |
$begingroup$
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::NTuple2,UnionTree,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.
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
$endgroup$
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::NTuple2,UnionTree,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.
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
edited Aug 6 at 19:47
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
answered Aug 6 at 10:39
user3263164user3263164
1513 bronze badges
1513 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
Aug 6 at 19:42
1
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
add a comment |
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
Aug 6 at 19:42
1
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
1
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
Aug 6 at 19:42
$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
Aug 6 at 19:42
1
1
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
$begingroup$
Yes, you're right. I corrected it, so that it's now actually 56 bytes
$endgroup$
– user3263164
Aug 6 at 19:49
add a comment |
$begingroup$
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 at 5:23
BrojowskiBrojowski
615 bronze badges
$endgroup$
add a comment |
$begingroup$
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 at 5:23
BrojowskiBrojowski
615 bronze badges
$endgroup$
add a comment |
$begingroup$
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 at 5:23
BrojowskiBrojowski
615 bronze badges
$endgroup$
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 at 5:23
BrojowskiBrojowski
615 bronze badges
answered Aug 6 at 5:23
BrojowskiBrojowski
615 bronze badges
answered Aug 6 at 5:23
BrojowskiBrojowski
615 bronze badges
answered Aug 6 at 5:23
BrojowskiBrojowski
615 bronze badges
615 bronze badges
add a comment |
add a comment |
$begingroup$
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)
Struct implementation is the following:
typedef struct T
struct T * l;
struct T * r;
int v;
T;
Try This on JDoodle
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
$begingroup$
This appears to be 117 bytes, though you can do<2for that last check instead
$endgroup$
– Jo King
Aug 6 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
Aug 7 at 0:06
add a comment |
$begingroup$
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)
Struct implementation is the following:
typedef struct T
struct T * l;
struct T * r;
int v;
T;
Try This on JDoodle
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
$begingroup$
This appears to be 117 bytes, though you can do<2for that last check instead
$endgroup$
– Jo King
Aug 6 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
Aug 7 at 0:06
add a comment |
$begingroup$
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)
Struct implementation is the following:
typedef struct T
struct T * l;
struct T * r;
int v;
T;
Try This on JDoodle
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
$endgroup$
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)
Struct implementation is the following:
typedef struct T
struct T * l;
struct T * r;
int v;
T;
Try This on JDoodle
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
edited Aug 7 at 0:07
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
answered Aug 6 at 21:33
T. SalimT. Salim
3522 silver badges14 bronze badges
3522 silver badges14 bronze badges
$begingroup$
This appears to be 117 bytes, though you can do<2for that last check instead
$endgroup$
– Jo King
Aug 6 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
Aug 7 at 0:06
add a comment |
$begingroup$
This appears to be 117 bytes, though you can do<2for that last check instead
$endgroup$
– Jo King
Aug 6 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
Aug 7 at 0:06
$begingroup$
This appears to be 117 bytes, though you can do
<2 for that last check instead$endgroup$
– Jo King
Aug 6 at 22:36
$begingroup$
This appears to be 117 bytes, though you can do
<2 for that last check instead$endgroup$
– Jo King
Aug 6 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
Aug 7 at 0:06
$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
Aug 7 at 0:06
add a comment |
$begingroup$
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.
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
$endgroup$
add a comment |
$begingroup$
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.
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
$endgroup$
add a comment |
$begingroup$
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.
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
$endgroup$
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.
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
edited Aug 7 at 6:15
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
answered Aug 6 at 18:26
Chas BrownChas Brown
6,0991 gold badge6 silver badges25 bronze badges
6,0991 gold badge6 silver badges25 bronze badges
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f189285%2fwrite-the-shortest-program-to-check-if-a-binary-tree-is-balanced%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
May input be empty tree?
$endgroup$
– tsh
Aug 6 at 2:43
1
$begingroup$
In your initial example of a tree, if you remove the leaf
4, is the remaining tree balanced?$endgroup$
– Neil
Aug 6 at 8:43
$begingroup$
No, not that example, I meant the initial one, using ASCII art.
$endgroup$
– Neil
Aug 6 at 23:55
$begingroup$
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.
$endgroup$
– T. Salim
Aug 7 at 0:00
$begingroup$
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.
$endgroup$
– Geza Kerecsenyi
Aug 7 at 14:59