0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ (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? $\endgroup$
    – greybeard
    Jan 19 at 10:57
  • $\begingroup$ Sure every function in O(n log n) is in O(n^2). But we expected lowest bound. GeeksForGeeks claimed O(n^2). $\endgroup$
    – Ali Naseri
    Jan 19 at 14:57
  • $\begingroup$ geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced $\endgroup$
    – Ali Naseri
    Jan 19 at 14:58
  • $\begingroup$ 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. $\endgroup$ Jan 19 at 15:07
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 19 at 20:18

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.