r/badcode • • Jun 19 '21

typescript Check if binary tree is balanced...

Post image
221 Upvotes

44 comments sorted by

123

u/pedro823 Jun 19 '21

Frankly, LGTM. Not hard to understand, variables with somewhat decent names, and no blatant optimizations to be seen.

22

u/SuitableDragonfly Jun 20 '21

Me too. I was sitting here wondering if I was just really stupid to not see how this is bad.

5

u/paulsmithkc 👨‍🏫 Jun 20 '21

This looks like awesome code to me. Well documented, good variable names, super easy to read, easy to test, and sufficiently optimized.

This is a great example of where tuples work well, and how to use them in a recursive function.

High five to whoever wrote the code, I'm sure they'd be be a great team member to have.

6

u/[deleted] Jun 20 '21

In principle there's a way to terminate earlier. As soon as you find an unbalanced subtree you know the second argument is always going to be false

-62

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.

69

u/dliwespf Jun 19 '21

Since this seems to be your own code: Don't shame yourself, your code is quite alright.

And additionally: You seem to try to improve your own coding style. So in my opinion you are doing well!

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 use leftHeight == rightHeight instead 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 awkward abs check is required.

2

u/F54280 Jun 20 '21

Excellent catch, thx.

-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:
        0

if i were trying to be cheaky in python:

 return l.height == r.height and l.height or 0 + 1

which 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

u/btwiusearch Jun 19 '21
getHeightBalanceTupl

The weird thing is that the e is missing.

0

u/[deleted] 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

u/[deleted] 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

u/[deleted] Jun 19 '21

Can’t find the bad code here...

36

u/sohang-3112 Jun 19 '21

If this is bad code, then what is good code?

18

u/12wh Jun 19 '21

Dude, are you flexing?

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!

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

u/[deleted] 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

u/[deleted] Jun 20 '21

Ah I conflated “balanced” with “bushy” (I think that’s the word)

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

u/sixtyfifth_snow Jun 20 '21

Quite decent for me. Any problems?

-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

u/[deleted] 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, !optout

1

u/BenjaminGeiger Jun 20 '21

Get thee to a nunnery, go.