Solving Balanced Binary Tree - Leetcode problem

ajith manmadhanajith manmadhan
2 min read

In the cinematic adaptation of this challenge, we find ourselves on an intriguing quest to determine the balance of a mystical binary tree. Our mission is to unveil the tree's equilibrium, where the difference between the heights of the Left Subtree (LST) and Right Subtree (RST) is no more than 1.

https://leetcode.com/problems/balanced-binary-tree/

Math.abs(LST_Height - RST_Height) <= 1.   --> Tree is balanced

Our journey begins with a postorder traversal, an exploration strategy suited for our enigmatic task. During our odyssey, we meticulously calculate the height of each node, a vital piece of information. The height of a node, we discern, is the grander of the heights of its LST and RST.

Height of a Node = Math.max(LST_Height, RST_Height) + 1

As we delve deeper into the forest of nodes, we scrutinize the height difference, ensuring it remains within the confines of balance.

The narrative unfolds with an assumption that the tree, like any good story, is inherently balanced. Yet, our vigilant traversal harbors the power to unveil any imbalances lurking in the shadows. Should the height conditions falter, a revelation of imbalance shatters our illusion, and we exit our quest immediately, having uncovered the truth of this captivating binary tree.

/**
 * 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}
 */

/*
    TC: O(N)
    SC: O(Height of the tree)
*/

const postorder = (node) => {
    if(node === null) return 0;
    let leftheight = postorder(node.left);
    let rightheight = postorder(node.right);
    /* 
        The idea is that we assume that the tree is balanced by default. 
        If the height condition fails during the traversal we say it is unbalanced and exit         immidietly
    Height of LST - Height of RST <= 1 -->. height balanced
    */
    let diff = Math.abs(leftheight - rightheight);
    if(diff > 1) {
        return 'not balanced';
    }
    if(leftheight === 'not balanced' || rightheight === 'not balanced') return 'not balanced'
    return Math.max(leftheight, rightheight) + 1;
}

var isBalanced = function(root) {
    let res = postorder(root);
    // console.log({res})
    if(res === 'not balanced') return false;
    return true;
};
0
Subscribe to my newsletter

Read articles from ajith manmadhan directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

ajith manmadhan
ajith manmadhan