Time Complexity: Determining if a binary tree is balanced

I found an algorithm for determining if a binary tree is height-balanced. It Gets the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.

algorithm code:

/* CPP program to check if
a tree is height-balanced or not */

#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class Node {
public:
int data;
Node* left;
Node* right;
Node(int d)
{
int data = d;
left = right = NULL;
}
};

// Function to calculate the height of a tree
int height(Node* node)
{
// base case tree is empty
if (node == NULL)
return 0;

// If tree is not empty then
// height = 1 + max of left height
// and right heights
return 1 + max(height(node->left), height(node->right));
}

// Returns true if binary tree
// with root as root is height-balanced
bool isBalanced(Node* root)
{
// for height of left subtree
int lh;

// for height of right subtree
int rh;

// If tree is empty then return true
if (root == NULL)
return 1;

// Get the height of left and right sub trees
lh = height(root->left);
rh = height(root->right);

if (abs(lh - rh) <= 1 && isBalanced(root->left)
&& isBalanced(root->right))
return 1;

// If we reach here then tree is not height-balanced
return 0;
}

// Driver code
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->left->left->left = new Node(8);

if (isBalanced(root))
cout << "Tree is balanced";
else
cout << "Tree is not balanced";
return 0;
}


Claimed this code has O(n^2) complexity but I can not understand why. I think the worst case is when the Binary Tree is full, and in this case, the height of BST is log n that in every level it runs the height function with O(n) complexity. So I think I must have O(n log n) time complexity.

• (Tag runtime-analysis.) Note that every function in $O(n\log n)$ is in $O(n^2)$, too. Succinct pseudo code is preferred here over somewhat verbose code in a somewhat verbose programming language. Who claimed $O(n^2)$? What is the complexity for a completely degenerate tree, say, only left children? Commented Jan 19 at 10:57
• Sure every function in O(n log n) is in O(n^2). But we expected lowest bound. GeeksForGeeks claimed O(n^2). Commented Jan 19 at 14:57
• geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced Commented Jan 19 at 14:58
• See, the answer is in your link, your code is $O(n^2)$, while there is an $O(n)$ alternative code there. You said it yourself the height of BST is log n that in every level it runs the height function with O(n) complexity, we are calculating time complexity so we care about the height function complexity, not height itself. Commented Jan 19 at 15:07
• Please replace your C++ code with concise pseudocode. We are not a coding site and I expect that questions about a bunch of code are likely off-topic here. Not everyone here reads C+++ code, and asking someone to read all of that code is asking a lot.
– D.W.
Commented Jan 19 at 20:18

1 Answer

Determining if a binary tree is balanced runs in $$O(n)$$, since we only need to traverse each node once, and moving from one node to another requires $$O(1)$$ moves.

However, since your code calculates height from scratch repeatedly, it runs in $$O(n^2)$$.