1
$\begingroup$

I am having trouble finding the time complexity of the below code.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if root is None:
            return True

        def height(root):
            if root is None:
                return 0
            left = height(root.left)
            right = height(root.right)

            return 1 + max(left, right)


        def check(root):
            if root is None:
                return True


            if abs(height(root.left) - height(root.right)) < 2:
                return(check(root.left) and check(root.right))
            else:
                return False


        return check(root)

Is it O(n^2) or O(n) because first we are checking for the root, and that takes O(n) time and then we check for the left subtree and the right subtree, where the elements searched are halved each time?

Thanks!

$\endgroup$
2
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Jul 15, 2018 at 8:52
  • $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$
    – Raphael
    Jul 15, 2018 at 8:52

2 Answers 2

2
$\begingroup$

Your code has worst-case complexity $\Omega(n^{1.5})$. Consider a tree of height $h$ which is composed of a "backbone" of $h$ nodes, out of the $i$th of which (counting from the root) there is a path to the right ending at depth $h$. As an example, here is the case $h=4$: enter image description here

The height is computed along the entire backbone. The subtree rooted at the backbone node of depth $h-\ell+1$ has $\binom{\ell+1}{2}$ nodes (where $\ell=1$ corresponds to the backbone's leaf), and so computing the height of all subtrees along the backbone takes time proportional to $$ \sum_{\ell=1}^h \binom{\ell+1}{2} = \binom{h+2}{3} = \Theta(h^3). $$ In contrast, the tree contains $\binom{h+1}{2} = \Theta(h^2)$ nodes, so the running time in this case is $\Omega(n^{1.5})$ (in fact, it is $\Theta(n^{1.5})$ in this particular case).

$\endgroup$
3
  • $\begingroup$ why are you saying $Ω(n^{1.5})$ is the WORST case? doesn't $Ω$ mean that the time complexity is at least $Ω(n^{1.5})$ ? because I'm pretty sure bigO means worst case(less than or equal) and $Ω$ means best case (more than or equal) $\endgroup$
    – John P
    Jul 15, 2018 at 7:27
  • $\begingroup$ @JohnP Here is a primer on these matters: cs.stackexchange.com/questions/23068/…. $\endgroup$ Jul 15, 2018 at 7:29
  • $\begingroup$ I am not claiming that my example is the worst case. It does show, however, that the worst case complexity is at least $\Omega(n^{1.5})$. $\endgroup$ Jul 15, 2018 at 7:29
0
$\begingroup$

Imagine you have left and right graph each with n nodes. Define complexity of check as $C(n)$ and complexity of height as $H(n)$. Complexity of height calculation $H(2n) = 2H(n)$ is linear or $H(n)\approx O(n)$.

Now complexity of check

$C(2n)=2C(n)+2H(n)=2\big(2C(n/2)+2H(n/2)\big)+2H(n)=$

$=4C(n/2)+4H(n/2)+4H(n/2)=4C(n/2)+8H(n/2)=$

$=...=2nC(1)+(2n\log_2 2n)H(1)$

So overall complexity is $O(n\log n)$.

It is unexpectedly good. At first I thought it will be worse than $O(n^2)$.

The algorithm can be improved to $O(n)$ if you combine height and check functions and return height and check together:

def height_and_check(root):
# returns height and check pair
    if root is None:
        return 0, True

    left_height, left_check = height_and_check(root.left)
    right_height, right_check = height_and_check(root.right)

    height = 1 + max(left_height, right_height)

    check = abs(left_height - right_height) < 2 \
            and left_check \
            and right_check

    return height, check
$\endgroup$
3
  • $\begingroup$ You're tacitly assuming that the tree is balanced. This only holds in the "Yes" cases. $\endgroup$ Jul 14, 2018 at 20:47
  • $\begingroup$ Thank you for the new approach Ivan! If the tree is balanced, the complexity will be O(nlogn) or is it for the worst case? $\endgroup$ Jul 14, 2018 at 20:52
  • $\begingroup$ O(nlogn) is the complexity of the algorithm in the question in the worst case where n is the number of nodes. $\endgroup$ Jul 15, 2018 at 19:12

Your Answer

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

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