LeetCode Balanced Binary Tree: DFS and O(N) Time

Overview

LeetCode Balanced Binary Tree Solution: DFS to get the height of every subtree rooted at each node and test it against the balance definition, all in O(N) pass.

LeetCode Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Analysis: DFS and O(N) Time

This is just a simple application of DFS, just do a depth first search and each subtree whether it is balanced by the definition, if all subtree satisfy, then the whole tree is balanced, the time complexity is O( V + E ), linear to the number of nodes plus the number of edges. The additional effects is that we can get all the height in a single pass with O(N) time. The following code is accepted by the LeetCode OJ to pass this Balanced Binary Tree problem:
class Solution {
    public:
        int dfs(TreeNode *root, bool *pFlag) {
            if (NULL == root || false == *pFlag )
                return 0;

            int l = dfs(root->left, pFlag);
            int r = dfs(root->right, pFlag);
            *pFlag = *pFlag && (abs(l - r) <= 1);

            return max(l, r) + 1;
        }

        bool isBalanced(TreeNode *root) {
            bool ret = true;
            dfs(root, &ret);
            return ret;
        }

};

Remarks

  1. To get all the heights of every node in a tree, we also only need one DFS with the time complexity as O( V + E )
  2. Tree needs to use struct to define node, and there is a post about C/C++ struct “ The Usage of C/C++ struct”

Summary

LeetCode Balanced Binary Tree Solution: DFS to get the height of every subtree rooted at each node and test it against the balance definition, all in O(N) pass.

Written on January 13, 2013