Linked list in binary tree

Linked List Tree Depth-First Search Binary Tree

51.9% acceptance

Feb 25, 2026

3024

Given a binary tree root and a linked list with head as the first node. Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False. In this context downward path means a path that starts at some node and goes downwards.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_sub_path(
    head: Option<Box<crate::ListNode>>,
    root: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>,
  ) -> bool {
    fn matches(
      list: Option<&Box<crate::ListNode>>,
      tree: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>,
    ) -> bool {
      match list {
        None => true,
        Some(l) => match tree {
          None => false,
          Some(t) => {
            let t = t.borrow();
            if t.val == l.val {
              matches(l.next.as_ref(), t.left.clone()) ||
              matches(l.next.as_ref(), t.right.clone())
            } else {
              false
            }
          }
        }
      }
    }
    fn dfs(
      list: &Option<Box<crate::ListNode>>,
      tree: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>,
    ) -> bool {
      match tree {
        None => false,
        Some(t) => {
          let tb = t.borrow();
          if matches(list.as_ref(), Some(t.clone())) { return true; }
          dfs(list, tb.left.clone()) || dfs(list, tb.right.clone())
        }
      }
    }
    dfs(&head, root)
  }
}