Linked List in Binary Tree - Practice Coding Problems

Linked List in Binary Tree - Problem

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.

Input & Output

Example 1 — Path Found

$ Input: root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3], head = [4,2,8]

› Output: true

💡 Note: The path 4→2→8 exists in the tree starting from the left node with value 4, going right to 2, then right to 8

Example 2 — Path Not Found

$ Input: root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3], head = [1,4,2,6]

› Output: false

💡 Note: No downward path in the tree matches the sequence 1→4→2→6 from the linked list

Example 3 — Single Node Match

$ Input: root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3], head = [1]

› Output: true

💡 Note: Single node 1 exists in the tree, so the path is found

Constraints

The number of nodes in the tree will be in the range [1, 2500]
The number of nodes in the list will be in the range [1, 100]
1 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Binary tree and linked list with values to match

Try each tree node as potential starting point for linked list

Match

Check if downward path from node matches linked list sequence

Key Takeaway

🎯 Key Insight: The linked list can start from any tree node, not just the root - use DFS to check all possibilities

Asked in

M Microsoft 15 a Amazon 12 G Google 8 f Facebook 6

The key insight is that the linked list path can start from any tree node, not just the root. Best approach uses DFS with path matching - traverse every tree node and check if it can be the starting point of the linked list path. Time: O(n × m), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS	O(n × m)	O(h)	Use two separate DFS functions for finding start points and matching paths
Brute Force DFS	O(n × m)	O(h)	Check every tree node as potential starting point for the linked list path

Optimized DFS — Algorithm Steps

DFS traverse to find all tree nodes
For each node, use separate DFS to match linked list
Return true on first successful match

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Find

Main DFS visits each tree node

Path Match

For each node, separate function checks if linked list matches

Early Return

Return immediately when first match is found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool isPath(struct TreeNode* treeNode, struct ListNode* listNode) {
    if (!listNode) return true;
    if (!treeNode || treeNode->val != listNode->val) return false;
    return isPath(treeNode->left, listNode->next) || isPath(treeNode->right, listNode->next);
}

bool dfs(struct TreeNode* node, struct ListNode* head) {
    if (!node) return false;
    if (isPath(node, head)) return true;
    return dfs(node->left, head) || dfs(node->right, head);
}

bool solution(struct TreeNode* root, struct ListNode* head) {
    if (!head) return true;
    return dfs(root, head);
}

struct TreeNode* createTreeNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct ListNode* createListNode(int val) {
    struct ListNode* node = malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

int main() {
    // For simplicity, we'll create a basic test case
    struct TreeNode* root = createTreeNode(1);
    root->left = createTreeNode(4);
    root->right = createTreeNode(4);
    root->left->right = createTreeNode(2);
    root->left->right->left = createTreeNode(1);
    root->right->left = createTreeNode(2);
    root->right->left->left = createTreeNode(6);
    root->right->left->right = createTreeNode(8);
    root->right->left->right->left = createTreeNode(1);
    root->right->left->right->right = createTreeNode(3);
    
    struct ListNode* head = createListNode(4);
    head->next = createListNode(2);
    head->next->next = createListNode(8);
    
    bool result = solution(root, head);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Visit each of n tree nodes, for each node potentially traverse m linked list nodes to verify match

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth limited by maximum tree height h

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

985 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler