Matching Leaf Trails

Easy

Walk over the leaves of a binary tree (nodes with no children) from left to right and write down their values: that is the tree's leaf sequence. Given the roots of two trees, first and second, return True if their leaf sequences are exactly the same, order included, and False otherwise. Inner nodes and the shape of the trees do not matter.

Example 1

first=tree_node([4, 2, 9, 1, 3]), second=tree_node([7, 1, 8, None, None, 3, 9]) → True

The leaves of the first tree, left to right, are 1, 3, 9. The second tree's leaves are 1, 3, 9 as well, even though the shapes differ.

Example 2

first=tree_node([5, 6, 2]), second=tree_node([5, 2, 6]) → False

Same leaves, different order: 6, 2 versus 2, 6.

Example 3

first=tree_node([10]), second=tree_node([3, 10]) → True

A root without children is itself a leaf, so both trees have a single leaf, 10.

Constraints

1 ≤ number of nodes in each tree ≤ 200
0 ≤ Node.val ≤ 200

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Left, Node, Right Easy Identical Trees Easy Mirror-Image Tree Easy Tree Height Easy Evenly Grown Tree Easy

Input

first=tree_node([4, 2, 9, 1, 3]), second=tree_node([7, 1, 8, None, None, 3, 9])

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.