Matching Phone Menus

Easydepth-first searchAlso known as Same Tree

A clinic runs two phone lines, one for each office. Callers hear a recorded message, then press 1 or 2, then hear the next message, and so on until they reach a final message. Each message is a numbered recording, so each line's menu is a binary tree: press 1 goes left, press 2 goes right.

The menus are supposed to be copies of each other. After a messy update, the manager wants to know if they still are: same recording at every step, with the same keys leading to the same places.

Your task

Write sameMenu(first, second). Return true if the two trees are identical: the same shape, and the same value in every matching position. Otherwise return false.

Two empty trees are identical. Trees are shown in level order, like [7, null, 1], where null marks a missing child. Your function receives real TreeNode objects (or null) with val, left and right.

sameMenu(first: TreeNode, second: TreeNode) → bool

Examples

Example 1

Input

first = [4, 2, 6, 1, 3]
second = [4, 2, 6, 1, 3]

Output

true

Why

Both lines start with recording 4. Press 1 gives 2 on both, press 2 gives 6 on both, and below 2 the keys lead to 1 and 3 on both. Every step matches.

Example 2

Input

first = [7, 1]
second = [7, null, 1]

Output

false

Why

Both menus contain recordings 7 and 1, but on the first line you reach 1 by pressing 1, and on the second by pressing 2. Same recordings, different menu, so the answer is false.

Constraints

0 ≤ number of messages in each menu ≤ 1,000
-10,000 ≤ recording number ≤ 10,000
Recording numbers may repeat. Each tree is at most 500 levels deep.

Start with brute force

Write each tree out as a list, then compare the two lists. Many people try an in-order or pre-order list of values, and that is wrong: [7, 1] and [7, null, 1] both give the pre-order list 7, 1, yet they are different menus. The list must also record the missing children, as the level-order format does.

With the nulls included, the list approach is correct and O(n), but it builds two full lists before comparing anything. Walking both trees side by side uses no lists and stops at the very first difference.

Hints

0 of 4 shown

Hint 1
In the second example both menus hold the same two recordings. What exactly is different about them, and would a list of all recordings notice it?
Hint 2
Two menus match when their first recordings match, their press-1 menus match, and their press-2 menus match. Those last two are the same question on smaller trees.
Hint 3
Think about the stopping cases. What if both sub-menus are missing? What if only one of them is missing?
Hint 4
Recursion on both trees at once: if both nodes are null, return true. If exactly one is null, return false. Otherwise return a.val === b.val and same(a.left, b.left) and same(a.right, b.right).

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Walk both menus together, pressing the same key on both phones at each step. At every step there are three outcomes: both lines have ended (fine), only one has ended (different shape), or both play a recording (compare them, then keep going on both keys).

Trace [4, 2, 6, 1, 3] against [4, 2, 6, null, 3]:

Start: 4 and 4 match. Go to press 1 on both.
2 and 2 match. Go to press 1 on both.
The first line plays recording 1, the second line has nothing there. Exactly one is null, so return false.

The && (and) stops early: once one comparison is false, the rest of the tree is never visited.

Reference solution

function sameMenu(first, second) {
  if (first === null && second === null) return true; // both ended
  if (first === null || second === null) return false; // only one ended
  return first.val === second.val
    && sameMenu(first.left, second.left)
    && sameMenu(first.right, second.right);
}

def same_menu(first, second):
    if first is None and second is None:  # both ended
        return True
    if first is None or second is None:   # only one ended
        return False
    return (first.val == second.val
            and same_menu(first.left, second.left)
            and same_menu(first.right, second.right))

TimeO(n)Each pair of matching positions is checked once, and the walk stops at the first difference.

SpaceO(h)The recursion stack holds one call per level, where h is the height of the smaller tree.

Learn the idea: Binary Trees Tree Traversals Recursion

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code