Runtime complexity of brute-force for determining balanced binary tree

Question

I have the following codes for the brute-force method to determine whether a binary tree is balanced or not:

public boolean IsBalanced(Node root)
{
  if (root == null) return true;
  return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
  && IsBalanced(root.left)
  && IsBalanced(root.right)
}

public int maxDepth(Node root)
{
  if (root == null) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

I don't understand why the worst case runtime complexity is O(n^2) when the tree is a skewed tree. What I think is that if the tree is skewed, then the line Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 would immediately find that the height of the left subtree of the root is over 1 more than the height of the root's right subtree. Then the time complexity of the skewed tree case should be O(n). What am I missing here? Thanks!

Which operation are you talking about? Following en.wikipedia.org/wiki/Binary_search_tree operations are O(n), O(log n) but tree sort is O(n²) — Daniel Argüelles
People are saying when the tree is skewed, the runtime complexity of the code is O(n^2). I just don't understand why it is O(n^2). My thinking is that if the tree is skewed (to the left, for example), to check the max depth of the root's left and right subtrees only takes O(n). It could be found the max depth of the root's left subtree is n, and the max depth of the right subtree is 0. So the first call of Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 will return false, and IsBalanced is returned. So I think when the tree is skewed, the runtime complexity should be O(n). — Ames ISU

Varun Teja Varun Teja · Accepted Answer · 2015-05-28T13:49:06

In the method IsBalanced(Node root) for a skewed tree when it first calls

maxDepth(root.left) it takes n recursive calls in maxDepth(root) now still the

root is not null in IsBalanced(Node root) then again it calls

maxDepth(root.left) now for n-1 times and so on.so the time complexity is sum of

first n natural numbers i.e O(n^2).

Runtime complexity of brute-force for determining balanced binary tree

1 Answers