137
u/SuperSmurfen Jun 19 '21 edited Jun 19 '21
What is bad about this? Looks pretty readable to me, good variable names (all though perhaps a bit verbose), and it's pretty much just the standard O(n) algorithm
www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced
4
u/F54280 Jun 20 '21 edited Jun 20 '21
Yeah, looks good to me.
Only improvement is to stop the height difference and just useleftHeight == rightHeightinstead of the ugly Math.abs and the extra variable. But that’s almost nothing.Edit: as pointed by /u/SuperSmurfen, I am wrong
12
u/SuperSmurfen Jun 20 '21
Except the height is allowed to differ by one. Take this balanced tree for example:
A \ B
leftHeight == 0,rightHeight = 1, yet it is balanced. That's why the awkwardabscheck is required.2
-55
u/MrPancholi Jun 19 '21
It does work, but I just thought that the tuple thing I did was a little weird.
I suck with algorithms so I though this was pretty far form the ideal solution.
54
u/Cotspheer Jun 19 '21
Well thats where you were wrong and right at the same time kiddo.
4
u/cyanNodeEcho Jun 19 '21 edited Jun 20 '21
okay i had to think, is it bc this solution only supports even powers of 2?
which are exponentially sparse so as n -> large this algo will give wrong answer almost with probabliltiy 1?
if absolutely balanced was in the question seems like u might be able to
if left.height == right.height: return height + 1 else: 0if i were trying to be cheaky in python:
return l.height == r.height and l.height or 0 + 1which would eliminate the tuple, but require wrapping the length as boole
also still learning please be gentle (θ‿θ)
edit: okay i looked at the official solution, def wasnt clear to me that max height wouldnt obscure relative differences in height.
but i understand now. still confused why you wouldnt just calc (max, min) and then wrap that in a compare in a different function, seems so much more understandable... but im not super well versed 😅
4
u/Cotspheer Jun 19 '21
As far my computer science skills go, its seems to be solid. To know if the tree itself is balanced one has to calculate the left and the right height of the tree and this for each subtree. https://www.programiz.com/dsa/balanced-binary-tree Basically this implementation in typescript.
The tuple thing is a convenient thing to return the depth and if it's balanced. I see this often in c# but I dislike the use of tuples because they don't provide a meaning like an interface or class would. So please do this for the ones coming after you. Nothing wrong to use a proper named return type.
1
u/cyanNodeEcho Jun 19 '21 edited Jun 20 '21
i think if else would return the height if it were balanced, max height is good as well if unbalanced?
3
0
Jun 19 '21
[deleted]
7
u/RFC793 Jun 19 '21
Who cares, it is just used internally by the recursion. You don’t have to provide or be concerned by it with the wrapper at the bottom.
0
Jun 19 '21
[deleted]
6
u/symberke Jun 20 '21
At least at a cursory glance at the problem you definitely need both pieces of information. With height defined as the maximum distance to a leaf node you can't determine if a tree descending from a given node is balanced given only the heights of its two children. Similarly you can't determine if the tree is balanced given only the fact that its two child trees are balanced.
84
36
18
12
u/tenfingerperson Jun 19 '21
This is a fine solution and you'd likely see these during an interview, which leaves little time for beautiful code (and this isn't even bad).
26
u/MurdoMaclachlan public boolean isInt(int i) { return true; } Jun 19 '21
Image Transcription: Code
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getHeightBalanceTupl(root: TreeNode | null): [number,boolean] {
if(root===null){
return [0,true];
}
const [leftHeight,isLeftBalanced] = getHeightBalanceTupl(root.left);
const [rightHeight,isRightBalanced] = getHeightBalanceTupl(root.right);
const height = 1 + Math.max(leftHeight,rightHeight);
const heightBalance = leftHeight - rightHeight;
return [height,isLeftBalanced && isRightBalanced && Math.abs(heightBalance)<=1];
}
function isBalanced(root: TreeNode | null): boolean {
return getHeightBalanceTupl(root)[1];
};I'm a human volunteer content transcriber for Reddit and you could be too! If you'd like more information on what we do and why we do it, click here!
14
19
u/seemslikesalvation Jun 19 '21 edited Jun 19 '21
This is fine to me. A binary tree is balanced if both its left and right subtrees are balanced. Recursive != bad by default. O(log n) recursive calls.
17
u/KlzXS Jun 19 '21
True that for recursive != bad, but this is still O(n) it visits every node once. Which makes sense. Given a random tree you can't tell if it's balanced unless you travese the whole thing.
7
u/fireflash38 Jun 20 '21
Given a random tree you can't tell if it's balanced unless you travese the whole thing.
You can still short circuit if you find one unbalanced subtree. The failing case doesn't need to hit every node.
2
u/seemslikesalvation Jun 19 '21
You’re right; l meant recursive depth is log N.
7
u/icendoan Jun 19 '21
Recursive calls is O(n): consider the degenerate tree with only left children. The full left hand side gets counted here, which is one for each node.
4
u/seemslikesalvation Jun 19 '21 edited Jun 19 '21
Shit, it’s been a long time since I studied DSA. Log N would be the lower bound. Is that big-Omega?
1
u/paulsmithkc 👨🏫 Jun 20 '21 edited Jun 20 '21
This algorithm will ALWAYS visit every node. So the lower, upper, and average are the same.
Stopping at the first unbalanced node would change the bounds to:
Lower 1: constant in the case that in the case where it is the first node that you check (technically 3rd node, but that is still constant time)
Upper N: if the tree is balanced you still have to check every node
Average lg(n): When you find an unbalanced node, you can skip checking all of the other children and parents. This relies on checking that left is balanced first, and skipping the recursive call on the right when needed.
const [leftHeight,isLeftBalanced] = getHeightBalanceTupl(root.left); if (!isLeftBalanced) return [leftHeight,isLeftBalanced]; const [rightHeight,isRightBalanced] = getHeightBalanceTupl(root.right); if (!isRightBalanced) return [rightHeight,isRightBalanced];This does break the calculation for the height of the tree, but there is no way to do both. (Ignoring memorization techniques.)
2
Jun 20 '21
Can’t you just traverse and check if any node has a single leaf node?
1
u/paulsmithkc 👨🏫 Jun 20 '21
You cannot. Two entire branches can be balanced in and of themselves. But if one has height 5 and the other height 3, the whole tree becomes imbalanced.
1
3
u/ske66 Jun 20 '21
I've been a software dev for 5 years now and I still have absolutely no idea what the hell a binary tree is or what its used for. Plz halp
0
-1
u/ef02 Jun 20 '21
The | null is unnecessary in TypeScript, but other than that, it seems fine.
3
u/MrPancholi Jun 20 '21
Why is null unnecessary? Wouldn't that cause a conflict with the type?
0
u/ef02 Jun 20 '21
Oh man...I wish I could answer any "why" question about JS/TS...but all I know is that the TS transpiler doesn't complain when I do something like that without the
| null😂I believe that setting an object type to null is fine, but undefined / unknown would cause an error.
2
u/RedMser Jun 20 '21
Depends on whether you set the TS compiler to strict mode or not. I personally prefer having to add null or undefined to the type, so you can avoid checking for null-ish values before every function call, as long as you aren't writing library code at least.
35
Jun 19 '21 edited Dec 21 '24
[removed] — view removed comment
13
u/Shakespeare-Bot Jun 19 '21
Just because thee don’t knoweth how a tuple worketh doesn’t maketh t lacking valor
I am a bot and I swapp'd some of thy words with Shakespeare words.
Commands:
!ShakespeareInsult,!fordo,!optout1
123
u/pedro823 Jun 19 '21
Frankly, LGTM. Not hard to understand, variables with somewhat decent names, and no blatant optimizations to be seen.