Interview Question: Balanced Binary Tree
Vložit
- čas přidán 28. 08. 2024
- Coding interview question from www.byte-by-byt...
In this video, I show how to determine whether a binary tree is balanced.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
50 Practice Questions: www.byte-by-by...
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
You can simplify the body of isBalanced to “return (balancedHeight(n) > -1);”
DAMN this is a clean solution. Good shit ByteByByte!
...
int h1 = balancedHeight(n.left);
if(h1 == -1) return -1;
int h2 = balancedHeight(n.right);
if(h2 == -1) return -1;
...
Could this save some time if h1 is not balanced?
Yeah you could totally do that. Doesn't change the big O complexity but does improve the average case
You do not have to invoke the balancedHeight method for the right subtree if h1 == -1.
You can also use tree traversal to calculate min and max height of the leaf
function isBalanced(node) {
let max = Number.MIN_SAFE_INTEGER;
let min = Number.MAX_SAFE_INTEGER;
const postFix = function(node, level) {
if(!node) {
max = Math.max(max, level);
min = Math.min(min, level);
return level;
}
const rLevel = postFix(node.right, level+1);
const lLevel = postFix(node.left, level+1);
const c = Math.max(rLevel, lLevel) + 1;
return c;
};
postFix(node, 0);
if(max-min < 2) {
return true;
}
return false;
}
Why does an unbalanced tree produce -1? Can you please show?
Great video just needed one clarification . Conceptual is slightly different from implementation right ?
The height of root node should be 2( as per definition of height) but we end up returning 3. Why are we doing so ?
I have the same question.Did you get your answers?
A small correction here , u mentioned in one of the statements that u cant overload methods becoz of different return types , but actually u can overload methods wid different return type as long as the parameters u pass r different in order ,type or number.
But height never gets values.... You do not add 1 during each recursive call???? What am I missing, Thanks good video!
please can you tell me the worst case complexity (Big-Oh) for this code in the video?
Do we really require if (h1 == -1 || h2 ==-1) statement? Without this even it is returning -1 in case of tree hight difference is > 1.
Why aren't the elements of the tree in order if the whole point of a binary search tree is to have every node be balanced from left to right?
A binary tree is not necessarily a binary search tree
why whould the height be -1?
We're just using -1 as an indicator that the tree is not balanced. That way if we have a positive value, we know that the tree is balanced AND the height is that value
I did this 2 years ago in school, cant believe people ask about trees in interviews. Do professionals ever deal with trees really? at least not implementing their own surely
You're highlighting a key point, which is that interviewing is a completely separate skill from actually working as a software engineer. Unfortunately, you need to know this for your interview despite it not being relevant to your actual work
I had my first software engineering interview last week, and they asked me to about binary tree's. I am so glad I watched this.
Did they ask you to actually implement one or did they just ask you to explain the concept?
they gave me code, asked me what it did. It instantly saw it was a BST, then they asked me about functions i would add to it, (insert, delete,balance,find,ect...) and i had to pseudo code the functions
Great video...very nice and simple explanation!! Thank you.
hey! great videos! I don't understand when/how h1 or h2 would could be -1? because we're not initializing them to -1? or is null -1 in integer?
basically the latter. int is a primitive type so it is initialized to 0. By setting them to -1 that is the equivalent of saying the value is null
hey can you please tell why we are checking this condition (h1 == -1 || h2 == -1) return -1;
I believe this is because we are checking if the left and right subtrees are balanced as well as the original tree. He is using -1 as an indicator that the subtree is not balanced (since -1 is not a valid height). If the left or right subtree is unbalanced then the entire tree is unbalanced, so we must make sure they are balanced before computing the height for our current root. I hope this is helpful :)
@@sniperbear2000 Thanks I got it
@@sniperbear2000 hi, can you pls talk about an example case where h1 or h2 == -1? I understand your explanation but unable to find a case where it hits -1 base
This was not easy, thinking to initialise the program to -1.
where did -1 come from in the helper method? how can h1 and h2 equal -1?
-1 has been used as an error code to indicate that the tree is not balanced (i.e., the difference in height between left and right subtree of a particular node is greater than 1). You could also use another value as an error code (e.g., Integer.MIN_VALUE). Actually, the height of an empty tree is defined to be -1, so it would be better to return -1 if n == null and INTEGER.MIN_VALUE as an error code.
I didn't understood Math.abs(h1 - h2) > 1. What exactly do you mean by "not more than one difference" ?
A binary tree in this case is not balanced if any subtree has a height of 2 or more than another subtree.
2:19 You are wrong about the definition of binary search tree height. It is as follows: The heights of two subtrees of any node are no more different than 1.
That's what I said. If the left subtree and the right subtree don't differ by more than 1
First of all, your definition of subtree is not correct based on the way you explains subtree height in your video. (You can check this link out: www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem.) Second, the left and right subtrees' heights differ by at most one, the left subtree is balanced, and the right subtree is balanced. The tree instance you showed is thus not a balanced tree.
Your definition of height here is incorrect.
1:24 is not Balacned. 3 LST length is 3 and RST is 0
How?