Review the AI
Counting Nodes
Three ways to count the nodes of a tree. Label them: correct, slow, buggy.Problem
size(node): return the number of nodes in the tree. Nodes have .left and .right (or None); an empty tree is None.Solution A
1def size(node):
2 count, queue = 0, [node] if node else []
3 while queue:
4 cur = queue.pop(0)
5 count += 1
6 for child in (cur.left, cur.right):
7 if child:
8 queue.append(child)
9 return count
Solution B
1def size(node):
2 if node is None:
3 return 0
4 if node.left is None and node.right is None:
5 return 1
6 return size(node.left) + size(node.right)
Solution C
1def size(node):
2 if node is None:
3 return 0
4 return 1 + size(node.left) + size(node.right)