Trees

Question 1

Invert Binary Tree

Answer 1

root.left, root.right = root.right, root.left
helper(root.left)
helper(root.right)

Question 2

Maximum Depth of Binary Tree

Answer 2

return 1 + max(maxDepth(root.left), maxDepth(root.right))

Question 3

Diameter of Binary Tree

Answer 3

self.diameter = 0

def helper(root):
if root is None: return 0
left = helper(root.left)
right = helper(root.right)
self.diameter = max(self.diameter, left + right)
return 1 + max(left, right)

helper(root)
return self.diameter

Question 4

Balanced Binary Tree

Answer 4

def helper(root):
if root is None: return 0

left  = helper(root.left)
if left == -1: return -1

right = helper(root.right)
if right == -1: return -1

if abs(left-right) > 1: return -1

return 1 + max(left,right)

return helper(root) != -1

Question 5

Same Tree

Answer 5

if p is None and q is None:
return True
elif p is None and q:
return False
elif q is None and p:
return False
else:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Question 6

Subtree of Another Tree

Answer 6

if not root: return False

if sameTree(root, subRoot): return True

return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Question 7

LCA

Answer 7

def helper(root, p, q):
if root is None: return None
elif root == p: return root
elif root == q: return root

left  = helper(root.left, p, q)
right = helper(root.right, p, q)

if left and right:
    return root
return left if left else right

Question 8

Level Order Traversal

Answer 8

while qe:
level_size = len(qe)
level = []

for _ in range(level_size):
    node = qe.popleft()
    level.append(node.val)
    if node.left: qe.append(node.left)
    if node.right: qe.append(node.right)

result.append(level)

Question 9

Count Good Nodes in Binary Tree

Answer 9

def helper(root, maxValue):
if root is None:
return
if root.val >= maxValue:
self.counter += 1
helper(root.left, max(maxValue, root.val))
helper(root.right, max(maxValue, root.val))

Question 10

Validate Binary Search Tree

Answer 10

def helper(root, low, high):
if root is None:
return True
if low >= root.val or high <= root.val:
return False
return helper(root.left, low, root.val) and helper(root.right, root.val, high)