Time Complexity: Determining if a binary tree is balanced

Question

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.

• greybeard: (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?
• Ali Naseri: Sure every function in O(n log n) is in O(n^2). But we expected lowest bound. GeeksForGeeks claimed O(n^2).
• Ali Naseri: geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced
• Kenneth Kho: 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.
• D.W.: 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.

Answer 1

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