Blind 75 · #27 · Trees

Same Tree

EasyParallel recursionTime O(n)Space O(h)

Same Tree is an easy Trees problem from the Blind 75. The key pattern is parallel recursion, and a good solution runs in O(n) time.

Problem

Determine whether two level-order binary trees have identical structure and values.

Input

[[1,2,3],[1,2,3]]

Output

true

Input

[[4,5,4],[4,4,5]]

Output

false

Input

[[],[]]

Output

true

Two trees are equal when both roots are empty, or both exist with equal values and equal left and right subtrees.

Compare structure as well as values; a missing child on one side is a difference.