DEV Community

ajithmanmu
ajithmanmu

Posted on

Solving Balanced Binary Tree - Leetcode problem

Originally published on my Hashnode blog — cross-posted here for the Dev.to community.

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)