Chain Down the Tree

Medium

You get a singly linked list chain and the root of a binary tree. Check whether the tree has a path that goes strictly downward (from some node to one of its children, then to one of that child's children, and so on) whose values match the values of chain exactly, in order, from its first node to its last. The path may start at any node, not only the root, and may stop anywhere, not only at a leaf. Return True if such a path exists and False otherwise.

Example 1

chain=list_node([3, 1]), root=tree_node([5, 3, 8, None, 1]) → True

The tree has the downward path 3 → 1, from the root's left child to its right child.

Example 2

chain=list_node([5, 8, 2]), root=tree_node([5, 3, 8, None, 1]) → False

The path 5 → 8 exists, but node 8 has no children, so 2 cannot follow.

Example 3

chain=list_node([5, 3, 1]), root=tree_node([5, 3, 8, None, 1]) → True

The path may also start at the root: 5 → 3 → 1.

Constraints

1 ≤ number of tree nodes ≤ 2500
1 ≤ number of list nodes ≤ 100
1 ≤ Node.val ≤ 100 in both the list and the tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Linked List Binary Tree

Similar problems

Tree Into a Right Chain Medium Is It a Search Tree? Medium Two Mixed-Up Nodes Medium Tree From a Sorted Chain Medium All Leaf Paths With a Given Total Medium

Input

chain=list_node([3, 1]), root=tree_node([5, 3, 8, None, 1])

Expected

True

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