# Easy Top Down && Bottom Up(beat 89.35%) Solutions in JAVA

• Top Down Solution, which is O(n^2) time complexity

``````public boolean isBalanced(TreeNode root) {
if (root == null) return true;
if (root.left == null && root.right == null) return true;
int left = depth(root.left);
int right = depth(root.right);
return Math.abs(left-right) <=1 && isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
return Math.max(depth(root.left),depth(root.right))+1;
}
``````

Bottom Up Solution, which is O(n) time complexity

``````public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int depth = depth(root);
if (depth == -1) return false;
else return true;
}
private int depth(TreeNode root) {
if (root == null) return 0;
int left = depth(root.left);
int right = depth(root.right);
if (left == -1 || right == -1 || Math.abs(left-right) > 1) return -1;
return Math.max(left,right)+1;
}``````

• Hi,
could you tell me why top - down solution is o(n^2) time complexity ?
my understanding is worst case would be linked list
then f(n) = o(n) + f(n-1) = o(n^2).