How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Backend Engineer candidates at Bytedance during technical interviews.

Determine If One Binary Tree Is a Substructure of Another

Quick Overview

This question evaluates practical tree traversal skills and the ability to implement structural matching between two binary trees. It tests recursive tree comparison, a core algorithmic competency commonly assessed in coding interviews for software and backend engineering roles.

Company: Bytedance

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Given two binary trees `A` and `B`, determine whether `B` is a **substructure** of `A`. `B` is a substructure of `A` if there exists some node in `A` such that the subtree of `A` rooted at that node **contains `B` as a top-down prefix**. Concretely, starting from that node in `A`, every node of `B` must match the corresponding node in `A` by value and by shape: whenever `B` has a left (or right) child, `A` must also have a left (or right) child with an equal value at the same relative position. Nodes that exist in `A` but not in `B` are ignored — `B` does not have to reach the leaves of `A`. An empty tree `B` (`null` root) is **not** considered a substructure of any tree. If `A` is empty, the answer is always `false`. Each tree is given as a level-order array where `null` marks a missing child. Node values are integers. ### Examples **Example 1** ``` A = [3, 4, 5, 1, 2] B = [4, 1] ``` Tree `A`: ``` 3 / \ 4 5 / \ 1 2 ``` Tree `B`: ``` 4 / 1 ``` Output: `true` Starting at the node with value `4` in `A`, `B`'s root `4` matches, and `B`'s left child `1` matches `A`'s left child `1`. `B` has no right child, so the right side of `A` is ignored. It is a valid substructure. **Example 2** ``` A = [3, 4, 5, 1, 2] B = [4, 1, 3] ``` Tree `B`: ``` 4 / \ 1 3 ``` Output: `false` Starting at `A`'s node `4`, the left child matches (`1` vs `1`) but `B` requires a right child `3` while `A`'s node `4` has right child `2`. No other node in `A` matches `B`'s root either, so `B` is not a substructure. **Example 3** ``` A = [] B = [1] ``` Output: `false` (`A` is empty). ### Constraints - The number of nodes in `A` is in the range $[0, 10^4]$. - The number of nodes in `B` is in the range $[0, 10^4]$. - $-10^4 \le \text{Node.val} \le 10^4$.

Quick Answer: This question evaluates practical tree traversal skills and the ability to implement structural matching between two binary trees. It tests recursive tree comparison, a core algorithmic competency commonly assessed in coding interviews for software and backend engineering roles.

Given two binary trees `A` and `B`, determine whether `B` is a **substructure** of `A`. `B` is a substructure of `A` if there exists some node in `A` such that the subtree of `A` rooted at that node **contains `B` as a top-down prefix**. Concretely, starting from that node in `A`, every node of `B` must match the corresponding node in `A` by value and by shape: whenever `B` has a left (or right) child, `A` must also have a left (or right) child with an equal value at the same relative position. Nodes that exist in `A` but not in `B` are ignored — `B` does not have to reach the leaves of `A`. An empty tree `B` (`null` root) is **not** considered a substructure of any tree. If `A` is empty, the answer is always `false`. Each tree is given as a level-order array where `null` marks a missing child. Node values are integers. ### Examples **Example 1** ``` A = [3, 4, 5, 1, 2] B = [4, 1] ``` Output: `true` — starting at the node with value `4` in `A`, `B`'s root `4` matches and `B`'s left child `1` matches `A`'s left child `1`. `B` has no right child, so the right side of `A` is ignored. **Example 2** ``` A = [3, 4, 5, 1, 2] B = [4, 1, 3] ``` Output: `false` — at `A`'s node `4` the left child matches (`1` vs `1`) but `B` requires a right child `3` while `A`'s node `4` has right child `2`. No other node in `A` matches `B`'s root. **Example 3** ``` A = [] B = [1] ``` Output: `false` (`A` is empty). ### Input format Your function receives two level-order arrays `A` and `B`. `null` (Python `None`) marks a missing child. Build the trees, then decide whether `B` is a substructure of `A`. Return a boolean. ### Constraints - The number of nodes in `A` is in the range $[0, 10^4]$. - The number of nodes in `B` is in the range $[0, 10^4]$. - $-10^4 \le \text{Node.val} \le 10^4$.

Constraints

0 <= number of nodes in A <= 10^4
0 <= number of nodes in B <= 10^4
-10^4 <= Node.val <= 10^4
Trees are given as level-order arrays where null marks a missing child
An empty B is never a substructure; if A is empty the answer is always false

Examples

Input: ([3, 4, 5, 1, 2], [4, 1])

Expected Output: True

Explanation: Starting at A's node 4, B's root 4 matches and B's left child 1 matches A's left child 1. B has no right child, so A's right side is ignored. Valid substructure.

Input: ([3, 4, 5, 1, 2], [4, 1, 3])

Expected Output: False

Explanation: At A's node 4 the left child matches (1 vs 1) but B requires right child 3 while A's node 4 has right child 2. No other A node matches B's root 4.

Input: ([], [1])

Expected Output: False

Explanation: A is empty, so the answer is always false.

Input: ([1, 2, 3], [])

Expected Output: False

Explanation: B is empty (null root), which is never a substructure of any tree.

Input: ([1], [1])

Expected Output: True

Explanation: Single-node B matches the single-node A by value.

Input: ([10, 12, 6, 8, 3, None, None], [12, 8])

Expected Output: True

Explanation: Starting at A's node 12, B's root 12 matches and B's left child 8 matches A's left child 8. Sparse positions in A (explicit None) are handled by the level-order builder.

Input: ([8, 8, 7, 9, 2, None, None, None, None, 4, 7], [8, 9, 2])

Expected Output: True

Explanation: The second 8 in A (left child of root) has children 9 and 2, matching B exactly. Demonstrates that the matching root may be deeper in A and that duplicate values force a full subtree check, not just a root-value match.

Input: ([1, 2, 2, 3, 3, 3, 3], [2, 3, 3])

Expected Output: True

Explanation: Either node 2 in A roots a subtree whose children are 3 and 3, matching B. Duplicate values throughout.

Input: ([-1, -2, -3], [-2])

Expected Output: True

Explanation: Negative values; B's single node -2 matches A's left child.

Input: ([4, 5, 6], [4, 5, 7])

Expected Output: False

Explanation: Near miss: B's left child 5 matches but B's right child 7 differs from A's right child 6, and no other A node has value 4.

Hints

Decompose the problem into two pieces: (1) for a FIXED node in A, does B match as a top-down prefix starting there? and (2) try every node of A as that fixed starting point.
The prefix-match helper bottoms out the moment B runs out of nodes (return true) — B does not need to reach A's leaves. It fails only when A is missing a node that B still requires, or the values differ.
Handle the empty cases up front: an empty B returns false, and an empty A returns false. Don't let an empty B accidentally match (a null B subtree DOES match during the recursive prefix check, but the overall empty-B input must short-circuit to false).

Quick Overview