HBBTREE - Editorial

editorial
1

Prerequisites: Binary Trees, Binary Trees Traversal Techniques.

Problem: Given a connected binary tree with N nodes, determine if it is height-balanced.

(Note: A binary tree is height-balanced if the depth of the two subtrees of every node never differs by more than one.)

Solution Approach: This problem also can be solved using a recursive approach to check if a binary tree is height-balanced. For each node, calculate the height of its left and right subtrees. If the heights differ by more than one, or if any subtree is unbalanced, the tree is considered unbalanced.

Algorithm:

    1. Implement a recursive function checkHeight() that calculates the height of the subtree rooted at a given node.
      • If the node is NULL, return 0 (base case).
      • Recursively calculate the height of the left and right subtrees.
      • If either subtree is unbalanced (height = -1), return -1.
      • If the heights of the left and right subtrees differ by more than 1, return -1.
      • Otherwise, return the height of the subtree as 1 + max(leftHeight, rightHeight).
    1. In the main function isHeightBalanced(), call checkHeight() with the root of the binary tree.
    1. Print “YES” if the tree is height-balanced and “NO” otherwise.

Time Complexity: O(N), as we need to traverse each node once.
Space Complexity: O(1), as we don’t need any extra space.