Grind 75 Question 12: Balanced Binary Tree
Another binary tree! I think I’ve got this. Sure. Mmmm…maybe not.
The Problem
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
The Initial Attempts
I don’t know what the heck I’m doing, but here we are. I am 100% certain this won’t work. But at least I tried?
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
let leftCount = 0;
let rightCount = 0;
while(root){
if(root.left){
leftCount +=1;
root = root.next
}
while(root){
if(root.right){
rightCount +=1;
root = root.next
}
if(leftCount == rightCount || (leftCount + 1) == rightCount || (rightCount + 1) == leftCount)) return true;
return false;
};After fixing all the missing curly braces it…runs and is accepted? But now I’m 100% that the additional test cases won’t pass. Oh yes, a bit of digging reveals it was a fluke. Time to consult Neetcode.
It is…a lot, and I’m not even sure I understand what’s going on, but let me see if I can code it up properly based on the explanation.
The Solution
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
function dfs(tree) {
if(tree == null){
return [true, 0];
}
let right = dfs(tree.right);
let left = dfs(tree.left);
let isBalanced = ((left[0] && right[0]) && Math.abs(left[1]-right[1]) <= 1);
return [isBalanced, 1+ Math.max(left[1], right[1])];
}
return dfs(root)[0];
};Okay, so. I understand like, 85% of this. Let me see if I can bring it to 100% with a line-by-line walkthrough.
First, this is a recursive, depth-first-search function. In case I needed to explain that. Here’s how it goes:
- The recursive function, dfs (for depth-first search), is created within isBalanced.
- If the tree is null, go ahead and return [true, 0] because yes — with zero levels, it is indeed balanced.
- If it’s not null, we go ahead and declare some stuff: right and left, which we’ll be operating on in a second, calls the dfs function we’re in. Yay, recursion! The variable isBalanced returns a boolean: if both left and right return true AND the difference between the number of levels under left and right (I think — this is the part I don’t quite understand) is one or zero, isBalanced returns true. If not, it returns false.
- The return statement returns an array of the boolean & 1+ the higher number of levels between left and right. Again, this is the part I don’t quite understand, but I guess if one of those is two, it’s bad news and means the tree isn’t balanced?
- Finally, the function is called and the first part, the boolean, is returned. If the tree is balanced, we return true; if not, false.
What I Learned
- It’s easier to ask for help sooner rather than later 😉
- More practice with recursion, which is still a little bit baffling to me. One day it will click. I know there’s an explanation in Cracking the Coding Interview, so I’ll see if that helps. And I’ll look up my old pal Back to Back SWE.
- I guess I was wrong about trees and nodes last time — one of the examples had the parent node as 20 and the left node as 15, right as 7. So I don’t know about things being in order or not. Gah!
Onward to finish the final question of Week 1. This has taken me…more than a week. And it’s eight weeks total. Google, here I come! Limpin’ along. Wait-a meeeee!
mins
read
