111. Check if Two Binary Trees Are Identical

Given two binary trees (each in level-order token format), print 'Yes' if they have the exact same structure and the exact same value at every corresponding node, otherwise print 'No'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). Both trees are given, one per line.

Input: Two lines, each a space-separated level-order token representation ('N' for missing children) of a binary tree - one tree per line. Output: Print 'Yes' if both trees have identical structure and identical values at every corresponding node, otherwise print 'No'.

1 <= number of nodes in each tree <= 10^5

This is the simplest of the tree-comparison family (identical, mirror, isomorphic) - understanding it first makes the cross-comparison logic in the other two much easier to reason about by contrast.

Check whether two binary trees have exactly the same shape and exactly the same values at every corresponding position. Brute force: Serialize both trees into strings (level-order or preorder with null markers) and compare the strings for equality - this works but does extra serialization work when a direct recursive comparison achieves the same result with the same time complexity, more directly. Optimised: A direct recursive comparison (values match, AND both subtrees match) can short-circuit the MOMENT any mismatch is found anywhere, without needing to fully serialize either tree first - often faster in practice since it can exit early on the first discrepancy.

Serialize each tree into a string using a preorder traversal that includes explicit null markers for missing children, then compare the two resulting strings character by character. This is correct because two trees have identical structure and values exactly when their null-inclusive preorder serializations match, but it requires fully building both strings up front before any comparison can happen, so no mismatch can be detected early. Time: O(n) Space: O(n)

Push the two roots into a single queue as a pair and repeatedly dequeue a pair of corresponding nodes, checking they're both null, both non-null with equal values, or otherwise returning false immediately; for matching non-null pairs, enqueue their left children together and their right children together. This compares the trees level by level and can stop as soon as any mismatch is found, rather than needing to fully materialize both serialized strings first. Time: O(n) Space: O(n)

Recursively compare the two trees node by node: if both current nodes are null, they match here; if exactly one is null or their values differ, the trees aren't identical; otherwise recurse on both left subtrees and both right subtrees and require both recursive calls to succeed. This short-circuits immediately on the very first difference found and, unlike the BFS version's explicit queue of pending pairs, only needs stack space proportional to the tree's height rather than its width, making it the most memory-efficient of the three. Time: O(n) Space: O(h) recursion stack

1. Recursively compare the two trees: their current node values must match. 2. Recursively compare both trees' left subtrees against each other. 3. Recursively compare both trees' right subtrees against each other. 4. Two absent (null) nodes at the same position are considered a match; one absent and one present is not.

Time: O(n) in the worst case (fully identical trees, requiring a full comparison) - often faster with early exit on a mismatch. Space: O(h) for the recursion stack.

Test two single-node trees with equal and with differing values, two trees of the same shape but one differing value, and trees where one has a node where the other has 'N'.

Be ready to contrast this with 'symmetric tree' and 'mirror of another tree' checks - all three use nearly identical recursive shapes, differing only in WHICH subtrees get compared against which (same-side for identical, cross-side for mirror/symmetric).