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!