Mirror, symmetry and subtrees

Questions 1 to 5 of 8

1. 1. What does this program print? ``python class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def invert(node): if node is None: return None old_left = node.left node.left = invert(node.right) node.right = invert(old_left) return node def show(node): if node is None: return "None" return "(" + str(node.value) + " " + show(node.left) + " " + show(node.right) + ")" root = TreeNode(5, TreeNode(3, None, TreeNode(4)), TreeNode(8, TreeNode(6), None)) invert(root) print(show(root)) ``

   (5 (3 None (4 None None)) (8 (6 None None) None))(5 (8 None (6 None None)) (3 (4 None None) None))(5 (8 (6 None None) None) (3 None (4 None None)))(5 (3 (4 None None) None) (8 (6 None None) None))
2. 2. What does this program print? ``python class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def is_mirror(a, b): if a is None and b is None: return True if a is None or b is None: return False return a.value == b.value and is_mirror(a.left, b.right) and is_mirror(a.right, b.left) def is_symmetric(root): return root is None or is_mirror(root.left, root.right) sym = TreeNode(7, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(4, TreeNode(2), TreeNode(1))) lopsided = TreeNode(7, TreeNode(4, TreeNode(1)), TreeNode(4, TreeNode(1))) print(is_symmetric(sym), is_symmetric(lopsided), is_mirror(sym.left, sym.right)) ``

   False False TrueTrue True TrueTrue False FalseTrue False True
3. 3. This is_mirror is meant to say whether a and b are mirror images. What is wrong with its two recursive calls? ``python def is_mirror(a, b): if a is None and b is None: return True if a is None or b is None: return False return a.val == b.val and is_mirror(a.left, b.left) and is_mirror(a.right, b.right) ``

   It pairs left with left and right with right, which is the same-tree pattern. A mirror must cross the pairs: a.left with b.right, and a.right with b.left.Nothing is wrong. Matching left with left is what a mirror does.It never checks for None, so it recurses forever on empty children.It returns True whenever both inputs are non-empty, without comparing values.
4. 4. This looks_symmetric is meant to say whether a tree is symmetric. Which input gives a wrong answer? ``python def looks_symmetric(root): return root is None or root.left.val == root.right.val ``

   A root 1 with children 2 and 3. The values differ, so the check says False, which is right.A root 1 whose left child 2 has a right child 3, and whose right child 2 has a right child 3. The check says True, but the tree is not symmetric.A root 1 whose left child 2 has a left child 3, and whose right child 2 has a right child 3. The check says True, which is right, because the tree is symmetric.An empty tree. The check says True, which is right, because an empty tree is symmetric.
5. 5. Why does the queue version of the symmetry check use deque and popleft() instead of a list with pop(0)?

   pop(0) must shift every other item one place left, so it gets slow on a long queue, while popleft() does not.A list cannot hold two items at once.popleft() returns the largest item, and pop(0) returns the smallest.A deque keeps its items in sorted order.