Leaf-Similar Trees

EasyTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

The **leaf sequence** of a binary tree is the list of its leaf values (nodes with no children) read from left to right. Given two non-empty binary trees root1 and root2, return true if their leaf sequences are exactly equal (same length, same values in the same order), and false otherwise. The shapes of the trees and their internal node values do not matter. Aim for O(n1 + n2) time.

Examples

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true
Both trees have leaf sequence [6,7,4,9,8].
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
The sequences are [2,3] and [3,2]; order matters.

Constraints

  • 1 <= number of nodes in each tree <= 200
  • 0 <= Node.val <= 200

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems