# 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