CODEWITHSUNDEEP
binary-treetime-complexity
Ames ISU
Ames ISU

Reputation: 407

Runtime complexity of brute-force for determining balanced binary tree

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!

Upvotes: 0

Views: 516

Answers (1)

Varun Teja
Varun Teja

Reputation: 523

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).

Upvotes: 1

Related Questions