Linked List in Binary Tree

medium linked list tree dfs

Problem

Given a linked list head and a binary tree root, return true if there is a top-down path in the tree whose values exactly match the list.

Inputhead = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Outputtrue

The path 4 → 2 → 8 appears as a downward chain in the tree.

head (csv)

tree (level-order, null allowed)

def is_sub_path(head, root):
    def dfs(node, cur):
        if cur is None: return True
        if node is None: return False
        nxt = cur.next if node.val == cur.val else head
        return dfs(node.left, nxt) or dfs(node.right, nxt)
    def start(node):
        if node is None: return False
        return dfs(node, head) or start(node.left) or start(node.right)
    return start(root)

function isSubPath(head, root) {
  function dfs(node, cur) {
    if (cur === null) return true;
    if (node === null) return false;
    const nxt = node.val === cur.val ? cur.next : head;
    return dfs(node.left, nxt) || dfs(node.right, nxt);
  }
  function start(node) {
    if (node === null) return false;
    return dfs(node, head) || start(node.left) || start(node.right);
  }
  return start(root);
}

class Solution {
    ListNode head;
    public boolean isSubPath(ListNode head, TreeNode root) {
        this.head = head;
        return start(root);
    }
    boolean dfs(TreeNode n, ListNode c) {
        if (c == null) return true;
        if (n == null) return false;
        ListNode nxt = n.val == c.val ? c.next : head;
        return dfs(n.left, nxt) || dfs(n.right, nxt);
    }
    boolean start(TreeNode n) {
        if (n == null) return false;
        return dfs(n, head) || start(n.left) || start(n.right);
    }
}

class Solution {
public:
    ListNode* H;
    bool isSubPath(ListNode* head, TreeNode* root) { H = head; return start(root); }
    bool dfs(TreeNode* n, ListNode* c) {
        if (!c) return true;
        if (!n) return false;
        ListNode* nxt = n->val == c->val ? c->next : H;
        return dfs(n->left, nxt) || dfs(n->right, nxt);
    }
    bool start(TreeNode* n) {
        if (!n) return false;
        return dfs(n, H) || start(n->left) || start(n->right);
    }
};

Explanation

We need to know if the linked list shows up as a straight top-down path somewhere in the tree. The plan is two layers of recursion: one to try starting the match at every tree node, and one to walk the list downward from a chosen start.

The inner dfs(node, cur) matches the list. If cur is None, we have consumed the whole list, so it is a success. If the tree node is None first, we ran out of tree, so it fails. When the values match, we advance to cur.next; otherwise we reset back to head to restart matching, then recurse into both children.

The outer start(node) kicks off a fresh dfs(node, head) at every node, and recurses left and right so no possible starting point is missed.

Example: head = [4,2,8]. We try starts until we land on a tree node valued 4 whose downward chain reads 4 → 2 → 8. Matching 4 advances to 2, then 8, then the list empties and we return true.

With N tree nodes and a list of length L, each start can re-scan up to L nodes, giving roughly O(N · L) time and O(H) recursion space.

Time: O(N · L) Space: O(H)