110. Balanced Binary Tree

EasyTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem presents a scenario where one is given a binary tree and is tasked with determining if the tree is height-balanced. In the context of this problem, a height-balanced binary tree is defined as a binary tree where the heights of the two child subtrees of any node differ by no more than one. Additionally, the subtrees of any node must also be height-balanced.

Intuition

The solution to this problem involves a recursive approach, where we traverse the tree to check the height of both left and right subtrees for each node and verify the balance condition (that the height difference is no more than one).

The intuition behind the solution is to perform a post-order traversal of the tree. A post-order traversal means we check the subtrees before dealing with the current node, which naturally allows us to check whether the subtrees are balanced and also to calculate their heights.

If at any point we find that the subtree is not balanced (i.e., the height difference between the left and right subtree is greater than 1), we can immediately conclude that the tree is not height-balanced.

The function height calculates the height of a tree rooted at a given node. If the left or right subtree is unbalanced (represented by a height of -1), or if the current node's subtrees' heights differ by more than 1, it returns -1, indicating that the tree is not balanced starting from this node. If the subtrees are balanced, the function returns the actual height, which is 1 plus the maximum of the heights of the left and right subtrees.

The isBalanced function calls the height function with the root node and checks if the returned value is non-negative. A non-negative return value indicates that the tree is balanced, whereas a value of -1 indicates that it is not.

By using this approach, we only need to traverse each node once, giving us an efficient algorithm with a time complexity of O(n) where n is the number of nodes in the tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How does quick sort divide the problem into subproblems?

Solution Approach

The solution implements a recursive function to determine the height of a given subtree and whether the subtree is balanced.

Within this approach, a few key concepts and algorithms are used:

  • Post-order Traversal: The function height uses post-order traversal of the tree. At each node, it first checks the height of its left and right subtrees before performing any action on the current node. Only after we have the heights of the subtrees do we check if they satisfy the balance criterion.

  • Recursion: Recursion is a fundamental part of the solution. The height function calls itself to find the height of the left subtree and the right subtree.

  • Termination Checks: The function includes condition checks to terminate early if an imbalance is found. When the left or right subtree has an imbalance (height of -1), or their height difference is more than 1, the function returns -1 immediately, avoiding further unnecessary checks or recursive calls.

  • Height Calculation: To calculate a subtree's height, the function considers the larger height of its left or right subtree and adds 1 to account for the current node.

Let's break down the code step-by-step:

  • We define the height function that takes a TreeNode as an argument. This function will return an integer representing the height of the tree rooted at the given node or -1 if the subtree is unbalanced:

    1def height(root):
2    if root is None:
3        return 0
4    l, r = height(root.left), height(root.right)
5    if l == -1 or r == -1 or abs(l - r) > 1:
6        return -1
7    return 1 + max(l, r)

  • If the current node root is None, which means we've reached the end of a branch, it returns 0 as the height.

  • It uses the same height function to get the height of the left and right subtrees.

  • The function checks if either l or r is -1, indicating that the respective subtree is unbalanced. It also checks if the absolute difference in heights abs(l - r) is greater than 1. If any of these conditions are true, the current subtree cannot be height-balanced and the function returns -1.

  • If all is well, the function computes the height of the current tree by adding 1 to the maximum of the heights of the left and the right subtrees.

  • The main function isBalanced calls the height function on the root and checks if the result is greater than or equal to 0. A result of -1 would mean the tree is not height-balanced:

    1class Solution:
2    def isBalanced(self, root: Optional[TreeNode]) -> bool:
3        return height(root) >= 0

This recursive solution is elegant and efficient because it computes both the balance status and height simultaneously, avoiding repeated calculations that would occur if we treated each concern separately.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the following binary tree:

1    3
2   / \
3  9  20
4    /  \
5   15   7

In this example, we have a binary tree where the root node has a value of 3, the left child is a leaf node with a value of 9, and the right child has a value of 20. The right child has its own children (15 on the left and 7 on the right), both leaf nodes.

Now, let's walk through the solution algorithm step-by-step:

  1. The isBalanced function will begin by calling the height function on the root node (with value 3).
  2. The height function checks if the root node is None. Since it's not, it proceeds to find the height of the left and right subtrees.
  3. The height function is recursively called on the left child (value 9) which is a leaf node. As it does not have any children, the function returns 1 because the height of a leaf node is 1.
  4. Similarly, the height function is recursively called on the right child (value 20).
  5. For node 20, the function calls itself on node 15 (left child) and node 7 (right child), both of which are leaf nodes and so return 1.
  6. Now, with l (the height of the left subtree of node 20) and r (the height of the right subtree of node 20) both equal to 1, the function proceeds to check if the subtree rooted at node 20 is balanced. Since abs(l - r) = 0 which does not exceed 1, it is balanced and the function returns 1 + max(l, r) = 2.
  7. Back at the root node (value 3), we now have l (the height of the left subtree) as 1 and r (the height of the right subtree) as 2. The function checks if the subtree rooted at node 3 is balanced. abs(1 - 2) equals 1, which is within the allowed difference, so it is balanced, and the function returns 1 + max(1, 2) = 3.
  8. Since there was no step where the height function returned -1, indicating an imbalance, the overall result of the height function when called on the root is the height of the tree 3, which is a non-negative number.
  9. The isBalanced function finally checks the returned value from the height function. Since the value is not -1, isBalanced returns True, indicating that the binary tree is indeed height-balanced.

Thus, using the given solution approach, the binary tree in our example has been determined to be height-balanced efficiently in O(n) time complexity, where n is the number of nodes in the tree.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def isBalanced(self, root: Optional[TreeNode]) -> bool:
10        # Helper function to calculate the height of a binary tree rooted at `node`.
11        def calculate_height(node):
12            # Base case: if the node is None, the height is 0.
13            if node is None:
14                return 0
15                      
16            # Recursively find the height of the left and right subtrees.
17            left_height = calculate_height(node.left)
18            right_height = calculate_height(node.right)
19          
20            # If either subtree is unbalanced (indicated by a height of -1),
21            # or the difference in heights is greater than 1, the tree is unbalanced.
22            if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
23                return -1
24          
25            # If the tree is balanced, return the height of the tree.
26            # Height of a node is 1 plus the maximum of the heights of its subtrees.
27            return 1 + max(left_height, right_height)
28      
29        # The tree is balanced if calculate_height does not return -1.
30        return calculate_height(root) >= 0
31
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;        // Variable for the value of the node.
6    TreeNode left;  // Pointer to the left child.
7    TreeNode right; // Pointer to the right child.
8
9    // Default constructor.
10    TreeNode() {}
11
12    // Constructor with the node's value.
13    TreeNode(int val) { this.val = val; }
14
15    // Constructor with the node's value, left, and right children.
16    TreeNode(int val, TreeNode left, TreeNode right) {
17        this.val = val;
18        this.left = left;
19        this.right = right;
20    }
21}
22
23class Solution {
24    /**
25     * Determines if a binary tree is balanced.
26     * In a balanced tree, the height of the two subtrees of any node never differ by more than one.
27     *
28     * @param root The root of the binary tree.
29     * @return true if the tree is balanced, false otherwise.
30     */
31    public boolean isBalanced(TreeNode root) {
32        // A non-negative height indicates that the tree is balanced,
33        // while -1 represents an imbalance.
34        return calculateHeight(root) >= 0;
35    }
36
37    /**
38     * Recursively calculates the height of a binary tree.
39     * Returns -1 if the subtree is unbalanced.
40     *
41     * @param node The node to calculate height of.
42     * @return The height of the tree if balanced, otherwise -1.
43     */
44    private int calculateHeight(TreeNode node) {
45        // Tree with no nodes has height 0.
46        if (node == null) {
47            return 0;
48        }
49
50        // Recursively find the height of the left and right subtrees.
51        int leftHeight = calculateHeight(node.left);
52        int rightHeight = calculateHeight(node.right);
53      
54        // Check if left or right subtree is unbalanced or if they differ in height by more than 1.
55        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
56            return -1; // Tree is not balanced.
57        }
58      
59        // Current node height is max of left and right subtree heights plus 1 (for the current node).
60        return 1 + Math.max(leftHeight, rightHeight);
61    }
62}
63
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    /**
16     * Checks if a binary tree is height-balanced.
17     * A binary tree is balanced if the depth of the two subtrees of every node 
18     * never differ by more than 1.
19     * 
20     * @param root A pointer to the root node of the binary tree.
21     * @return A boolean indicating whether the tree is balanced.
22     */
23    bool isBalanced(TreeNode* root) {
24        // Lambda function to recursively find the height of the tree.
25        // It returns -1 if the tree is unbalanced at any point.
26        std::function<int(TreeNode*)> findHeight = [&](TreeNode* node) -> int {
27            if (!node) {
28                // Tree is empty or this is a leaf node, hence the height is 0.
29                return 0;
30            }
31            int leftHeight = findHeight(node->left);
32            int rightHeight = findHeight(node->right);
33
34            if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
35                // If the left or right subtree is unbalanced, or if the current subtree
36                // is unbalanced (difference in height > 1), return -1 as an indicator.
37                return -1;
38            }
39            // Otherwise, calculate the height of this subtree,
40            // which is 1 + the maximum height of its left or right subtree.
41            return 1 + std::max(leftHeight, rightHeight);
42        };
43      
44        // If the height function returns -1, the tree is unbalanced.
45        // Otherwise, it is balanced.
46        return findHeight(root) >= 0;
47    }
48};
49
1// Function to determine if a binary tree is height-balanced
2// A binary tree in which the left and right subtrees of every node differ in height by no more than 1.
3function isBalanced(root: TreeNode | null): boolean {
4
5  // Helper function to compute the depth of the tree and check for balance
6  // Returns the height of a node or -1 if the subtree is not balanced
7  function depthFirstSearch(node: TreeNode | null): number {
8    // An empty node has a depth of 0
9    if (node == null) {
10      return 0;
11    }
12
13    // Recursively obtain the depth of the left subtree
14    const leftDepth = depthFirstSearch(node.left);
15    // Recursively obtain the depth of the right subtree
16    const rightDepth = depthFirstSearch(node.right);
17
18    // If the left or right subtree is not balanced, or the difference
19    // between their depths is more than 1, the current subtree is not balanced
20    if (leftDepth === -1 || rightDepth === -1 || Math.abs(leftDepth - rightDepth) > 1) {
21      return -1;
22    }
23
24    // Depth of current node is 1 plus the maximum depth of its left or right subtrees
25    return 1 + Math.max(leftDepth, rightDepth);
26  };
27
28  // The tree is balanced if the depth first search does not return -1
29  return depthFirstSearch(root) > -1;
30}
31
32// Definition for a binary tree node (given in the problem statement)
33interface TreeNode {
34  val: number;
35  left: TreeNode | null;
36  right: TreeNode | null;
37}
38
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

Time Complexity

The time complexity of the given recursive function is O(N), where N is the number of nodes in the Tree. Each node in the tree is visited once, and the height is calculated. The function returns -1 immediately if a subtree is found to be imbalanced, which eliminates the need for further computation on that subtree. The check for balance (abs(l - r) > 1) is O(1) for each node.

Space Complexity

The space complexity is O(H), where H is the height of the tree. This space is used by the call stack during the recursive calls. In the worst case scenario (a degenerate tree), the space complexity can become O(N), where each level of the tree has only one node, so the call stack grows to the height of the tree, which is N. In the best case scenario (a completely balanced tree), the space complexity would be O(log(N)), as the height of the tree would be log(N), representing the maximum number of recursive calls on the stack at any one time.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ