# 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:

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