Time Complexity of the code 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)) &lt; 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!
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$:


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