Binary Trees Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the whole module: traversals, rows, height, paths and rebuilding. Decide first which tool fits the clue in the problem, then write it. Try each task before you read the hint.
Compare two trees at once
Some problems walk two trees side by side. A mirror check compares the left side of one tree with the right side of the other. Two missing nodes match, one missing node does not.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))def mirror(a, b): if a is None or b is None: return a is b return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)print(mirror(root.left, root.right))Example 1 · Invert a tree
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def invert(node): if node: node.left, node.right = invert(node.right), invert(node.left) return node
def preorder(node): return [node.val] + preorder(node.left) + preorder(node.right) if node else []
print(preorder(root))print(preorder(invert(root)))[1, 2, 4, 5, 3, 6] [1, 3, 6, 2, 5, 4]
What this code does
- Every node swaps its two children. The recursive calls are made on the old right and left sides first, and then the pair is swapped.
- The second line is the mirror image: right subtrees come first.
a is b is True only when both are None. The values must match, and the outer children must match each other, and so must the inner ones. It is O(n).
Return two answers at once
A function can return a tuple. One walk then gives the height and the diameter together. Unpack the two answers of each child, combine them and send both upward.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def shape(node): if node is None: return 0, 0 lh, ld = shape(node.left) rh, rd = shape(node.right) return 1 + max(lh, rh), max(ld, rd, lh + rh)print(shape(root))Example 2 · Is it a search tree?
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightdef is_bst(node, low=float("-inf"), high=float("inf")): if node is None: return True if not low < node.val < high: return False return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)
good = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(8))bad = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(6)), TreeNode(8))print(is_bst(good), is_bst(bad))True False
What this code does
- Comparing a node only with its parent is not enough. The value 6 is larger than its parent 3, but it sits in the left subtree of 5.
- Passing a low and a high bound down catches this. Another way is to check that inorder is strictly increasing.
The height is 3 and the diameter is 4 edges. One pass of O(n) time replaces two. The same trick checks balance and height together.
Choose the tool from the clue
Row by row, shallowest first, or a view from one side points to a deque. A sorted order from a search tree points to inorder. A node that needs its children's answers points to postorder. A route from the root points to passing a value down. Two nodes that meet point to returning a value up.
Example 3 · Is one tree inside another?
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def same(a, b): if a is None or b is None: return a is b return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
def contains(big, small): if big is None: return small is None return same(big, small) or contains(big.left, small) or contains(big.right, small)
big = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(5))print(contains(big, TreeNode(4, TreeNode(1), TreeNode(2))))print(contains(big, TreeNode(4, TreeNode(1))))True False
What this code does
samecompares two trees node by node.containstriessameat every node of the big tree.- The second small tree is missing the node 2, so it is not a subtree. The cost is O(n times m) for sizes n and m.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Invert the tree 1 2 3 4 5 null 6 and print its rows as a list of lists.
[[1], [3, 2], [6, 5, 4]]
Exercise 2· Easy
Print True or False: is 1 2 2 3 4 4 3 symmetric?
True
Exercise 3· Easy
Print the sum of the values of all leaves that are left children in 3 9 20 null null 15 7.
24
Exercise 4· Medium
Print whether 5 3 8 2 4 7 9 and 5 3 8 2 6 7 9 are binary search trees, one per line.
True False
Exercise 5· Medium
A node is good if no node on the path from the root to it has a larger value. Print the number of good nodes in 3 1 4 3 null 1 5.
4
Exercise 6· Medium
Print the height and the diameter of 1 2 3 4 5 on one line, separated by a space, using one function that returns both.
3 3
Exercise 7· Hard
Turn the tree 1 2 3 null 4 back into level-order text with null for missing children, without trailing nulls.
1 2 3 null 4
Exercise 8· Hard
Build the tree with inorder [9, 3, 15, 20, 7] and postorder [9, 15, 7, 20, 3], then print its preorder list.
[3, 9, 20, 15, 7]
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Binary Trees