Recursion on Tree

Q: for each node in a tree, store the number of nodes in its left child subtree

• way of thinking:

1. what do you expect from your leaf child/ right child?
   total number of nodes in my left subtree
   total number of nodes in my right subtree
2. what do you want to do in the current layer?
   store the number of nodes in the left subtree
3. what do you want to return to your parent?
   same as number 1

def chang_subtree(node):
  if node is None:
    return 0
  left_total = change_subtree(node.left)
  right_total = change_subtree(node.right)
  node.total_left = left_total
  return 1 + left_total + right+total

Q: Find the node with the max difference in the total number of descendents in its left subtree and right subtree.

• way of thinking:

1. what do you expect from your leaf child/ right child?
   total number of nodes in my left subtree
   total number of nodes in my right subtree
2. what do you want to do in the current layer?
   diff = abs(left_total - right_total)
   global_max_diff = max(diff, global_max_diff)
3. what do you want to return to your parent?
   return 1 + left_total + right_total

global_max = -1
res = None

def node_diff(root):
  if root is None:
    return 0
  left_total = node_diff(root.left)
  right_total = node_diff(root.right)
  global global_max
  global res
  if abs(left_total - right_total) > global_max:
    global_max = abs(left_total - right_total)
    res = root
  return left_total + right_total + 1

Generally, choose root is None as base case. But sometimes, if we need something related to leaf, we need to choose leaf node( root.left is None and root.rightis None) as base case.

Q: Given a binary tree, find its minimum depth.

def minHeight(root):
  if root is None: #edge case
    return 0
  if root.left is None and root.right is None #base case
    return 1
#此处必须选他作为base case否则只有一个孩子的node会返回0
  left = minHeight(root.left) if root.left else float('inf') #infinity
  right = minHeight(root.right) if root.right else float('inf')
  return min(left, right) + 1

Q: Given a binary tree, write a function to determine whether this tree is a binary search tree

def BST(root): #这个function在这里有global的意味
  if root is None:
    return True
  min = float('-inf')
  max = float('inf')
  return isBST(root, min, max)

def isBST(root, min, max): #check the order of the values in the tree
  if root is None:
    return True
  if roo.val <= min or root.val >= max:
    return False
  return isBST(root.left, min, root.val) and isBST(root.right, root.val, max)

other ideas
a. use inorder traversal

#储存当前上一个节点的value到prev中，看它是不是比当前value小。对于root，prev node是left， 对于right，prev node是root。所以recursion中先找left，执行inorder left，存入prev，比较它与当前value，然后存当前value于prev中，执行inorder right
def is ValidBST(root):
  prev = [None]
  res = [True]
  inorder(root, prev, res)
  return res[0]
def inorder(root, prev, res):
  if not root:
    return
  inorder(root.left, prev, res)
  if prev[0] and prev[0] >= root.val:
    res[0] = False
  prev[0] = root.val
  inorder(root.right, prev, res)

b.

• way of thinking:

1. what do you expect from your leaf child/ right child?
   left_res: 左子树是否为BST/左子树最大值/左子树最小值
   right_res: 右子树是否为BST/右子树最大值/右子树最小值
2. what do you want to do in the current layer?
   isBST = left_res.isBST and right_res.isBST and lef_res.max < root.val and right_res.min > root.val
3. what do you want to return to your parent?
   return (isBST, left_res.min or root.val, right_res.max or root.val)

# in python: 12 or 25 = 12
#                  12 and 25 = 25
# if 25 == if True 和c++用法相同

def isBSTHelper(root):
  if not root:
    return (True, None, None)
  left_res = isBSTHelper(root.left)
  right_res = isBSTHelper(root.right)
  if not left_res[0] or not right_res[0]:
    return (False, None, None)
  if left_res[2] and root.val <= left_res[2]:
    return (False, None, None)
  if right_res[1] and root.val >= right.res[1]:
    return (False, None, None)
  return (True, left_res[1] or root.val, right_res[2] or root.val)

Q: Find the lowest Common Children

• way of thinking:

1. what do you expect from your leaf child/ right child?
   LCA found in the children
2. what do you want to do in the current layer?
   case 1: LCA found in both cases -> current root is LCA
   case 2: LCA found ar one side of children -> LCA found in the children
3. what do you want to return to your parent?
   LCA found in the children

def LCA(root, p, q)
  if not root:
    return None
  if root == p or root == q:
    return root
  left_res = LCA(root.left, p, q)
  right_res = LCA(root.right, p, q)
  if left_LCA and right_LCA:
    return root
  else if left_res:
    return left_res
  else:
    return right_res