Check Binary Tree is Height Balanced or Not

This class discusses how to check whether Binary Tree is Height Balanced or Not.

Readers can prepare a full competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given a binary tree.

Our task is to find whether the binary tree is height-balanced or not.

Time complexity: O(N)

Space complexity: O(N)

Example:

The below diagram shows the height-balanced tree example.

Condition: Left subtree height – Right subtree height = 0,1,-1.

The above condition should satisfy every node in the binary tree.

Logic:

We used a recursive function call to move on each binary tree node in our previous examples.

Here we use the same logic to move on the nodes.

Each time we need to return the height of the binary tree.

We returned the value based on the height from the left and right subtree functions.

Our focus should be on the return conditions.

We provided a step-by-step explanation in the video.

Code:

class Node:

    # Constructor to create a new node

    def __init__(self, val):

        self.data = val

        self.left = None

        self.right = None

class Solution:

    def isBalanced(self,root):

        if root is None:

            return 1

        lh = self.isBalanced(root.left)

        if lh == 0:

            return 0

        rh = self.isBalanced(root.right)

        if rh == 0:

            return 0

        if (abs(lh – rh) > 1):

            return 0

        else:

            return max(lh, rh) + 1

if __name__ == ‘__main__’:

    root = Node(1)

    root.left = Node(2)

    root.right = Node(3)

    root.left.left = Node(4)

    root.left.right = Node(5)

    root.right.left = Node(6)

    root.right.right = Node(7)

    root.right.left.right = Node(8)

    root.right.right.right = Node(9)

    print(“Double Linked List”)

    ob=Solution()

    z=ob.isBalanced(root)

    if(z>0):

        print(z)