Linked List in Binary Tree

Medium
1948.

Linked List in Binary Tree

Linked List in Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

You are given the head of a singly linked list and the root of a binary tree.

Return true if the values of the list, from the head onwards, appear in order along some downward path of the tree — a path that starts at any node and moves from parent to child at every step — and false otherwise.

Example 1

Input
head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output
true
Explanation
The right 4 → its child 2 → that node's child 8 spells 4, 2, 8.

Example 2

Input
head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output
true
Explanation
The downward path 1 → 4 → 2 → 6 starts at the root.

Example 3

Input
head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output
false
Explanation
6 and 8 are siblings, so no downward path continues from 6 to 8.

Constraints

  • 1 <= number of list nodes <= 100
  • 1 <= number of tree nodes <= 2500
  • 1 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSubPath = function(head, root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Linked List in Binary Tree — Solution in Python, Java & C++

Linked List in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Linked List in Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given the head of a singly linked list and the root of a binary tree.

Return true if the values of the list, from the head onwards, appear in order along some downward path of the tree — a path that starts at any node and moves from parent to child at every step — and false otherwise.

Example 1

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: The right 4 → its child 2 → that node's child 8 spells 4, 2, 8.

Example 2

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: The downward path 1 → 4 → 2 → 6 starts at the root.

Example 3

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: 6 and 8 are siblings, so no downward path continues from 6 to 8.

Constraints

  • 1 <= number of list nodes <= 100
  • 1 <= number of tree nodes <= 2500
  • 1 <= Node.val <= 100

Hints for Linked List in Binary Tree

  1. Hint 1

    The matching path can start at any tree node, so try every node as a starting point.

  2. Hint 2

    From a fixed start, matching is a simple recursion: the current tree node must equal the current list value, then either child must match the rest of the list.

  3. Hint 3

    Combine the two: dfs(node) returns whether a match starts at node, or inside its left subtree, or inside its right subtree.

How to solve Linked List in Binary Tree

Try each tree node as the start of the path; from a start, follow the list down the tree, branching to either child at each step.

Approach

  1. Read the list into an array a of length m.
  2. match(node, i): if i == m the whole list matched — true. If node is null or node.val != a[i], false. Otherwise return match(node.left, i + 1) or match(node.right, i + 1).
  3. search(node): if node is null, false; else match(node, 0) or search(node.left) or search(node.right).
  4. Return search(root).

Why it works

A downward path is fixed by its first node and the left/right choice at each step. search reaches every possible first node, and match tries both choices at every step while the values agree, so every candidate path is examined and nothing else is accepted.

Complexity

  • Time — O(n · min(m, h)) — each start explores at most m levels
  • Space — O(h) for the recursion

Pitfalls

  • After a mismatch, do not continue the same attempt one node lower — start a fresh attempt from that node instead (that is what search does).
  • Equal values on both children: try both branches, not only the first that matches.

Reference solution

Python

from typing import Optional

def isSubPath(head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
    a = []
    while head:
        a.append(head.val)
        head = head.next
    m = len(a)

    def match(node, i):
        if i == m:
            return True
        if node is None or node.val != a[i]:
            return False
        return match(node.left, i + 1) or match(node.right, i + 1)

    def search(node):
        if node is None:
            return False
        return match(node, 0) or search(node.left) or search(node.right)

    return search(root)

Java

public static boolean isSubPath(ListNode head, TreeNode root) {
    List<Integer> list = new ArrayList<>();
    for (ListNode cur = head; cur != null; cur = cur.next) list.add(cur.val);
    int[] a = new int[list.size()];
    for (int i = 0; i < a.length; i++) a[i] = list.get(i);
    return searchFrom(root, a);
}

static boolean searchFrom(TreeNode node, int[] a) {
    if (node == null) return false;
    return matchFrom(node, a, 0) || searchFrom(node.left, a) || searchFrom(node.right, a);
}

static boolean matchFrom(TreeNode node, int[] a, int i) {
    if (i == a.length) return true;
    if (node == null || node.val != a[i]) return false;
    return matchFrom(node.left, a, i + 1) || matchFrom(node.right, a, i + 1);
}

C++

bool searchFrom(TreeNode* node, const vector<int>& a);
bool matchFrom(TreeNode* node, const vector<int>& a, size_t i);

bool isSubPath(ListNode* head, TreeNode* root) {
    vector<int> a;
    for (ListNode* cur = head; cur; cur = cur->next) a.push_back(cur->val);
    return searchFrom(root, a);
}

bool searchFrom(TreeNode* node, const vector<int>& a) {
    if (!node) return false;
    return matchFrom(node, a, 0) || searchFrom(node->left, a) || searchFrom(node->right, a);
}

bool matchFrom(TreeNode* node, const vector<int>& a, size_t i) {
    if (i == a.size()) return true;
    if (!node || node->val != a[i]) return false;
    return matchFrom(node->left, a, i + 1) || matchFrom(node->right, a, i + 1);
}

JavaScript

var isSubPath = function(head, root) {
    var a = [];
    for (var cur = head; cur !== null; cur = cur.next) a.push(cur.val);
    return searchFrom(root, a);
};

var searchFrom = function(node, a) {
    if (node === null) return false;
    return matchFrom(node, a, 0) || searchFrom(node.left, a) || searchFrom(node.right, a);
};

var matchFrom = function(node, a, i) {
    if (i === a.length) return true;
    if (node === null || node.val !== a[i]) return false;
    return matchFrom(node.left, a, i + 1) || matchFrom(node.right, a, i + 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals