<!DOCTYPE html>

Linked List in Binary Tree

body { font-family: sans-serif; } h1, h2, h3 { text-align: center; } pre { background-color: #f0f0f0; padding: 10px; border-radius: 5px; overflow-x: auto; } img { display: block; margin: 0 auto; max-width: 100%; } .code-block { background-color: #f0f0f0; padding: 10px; border-radius: 5px; font-family: monospace; } .code-block pre { background-color: transparent; padding: 0; margin: 0; }

Linked List in Binary Tree

Introduction

This article delves into the fascinating problem of determining whether a linked list exists within the structure of a binary tree. This problem, posed in LeetCode as "1367. Linked List in Binary Tree", is an excellent exercise in understanding the interplay between data structures and algorithms.

The core challenge lies in navigating the inherent differences between linked lists and binary trees. While linked lists are linear structures, connecting nodes sequentially, binary trees exhibit branching and hierarchical relationships. Finding a linked list within a tree requires a methodical approach to match the sequence of nodes in the list against the tree's structure.

Problem Statement

Given a binary tree root and a linked list head , determine if the linked list is a subtree of the tree. A subtree of a binary tree is a tree that consists of a node in the original tree and all its descendants. For example, if the linked list is 1->2->3 , then the tree with root node 1 and its children 2 and 3 is a subtree of the given binary tree.

Key Concepts

Before diving into the solution, let's clarify some essential concepts:

Binary Tree: A data structure where each node has at most two children, typically referred to as the left and right child.
Linked List: A linear data structure where each node contains a value and a pointer to the next node in the sequence.
Subtree: A portion of a binary tree consisting of a node and all its descendants.
Depth-First Search (DFS): A graph traversal algorithm that explores as far as possible along each branch before backtracking.
Solution Approach
We'll employ a recursive approach to solve this problem. The key idea is to traverse the binary tree using depth-first search (DFS) and, at each node, attempt to match the linked list starting from that node. This matching process itself will be recursive.

Algorithm:

Base Cases:
- If head is empty (the linked list is empty), return True (an empty list is always a subtree).
- If root is empty (the tree is empty), return False (an empty tree cannot contain the list).
Matching Process:
- If head.val is equal to root.val , recursively check if the remaining nodes of the linked list ( head.next ) match the subtree rooted at the right child of the current node ( root.right ).
- If the above match succeeds, return True .
Recursive DFS:
- Recursively call the function on the left subtree ( root.left ).
- Recursively call the function on the right subtree ( root.right ).
- If either of these recursive calls return True , return True . Otherwise, return False .

Code Example (Python):

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSubPath(head, root):
    if not head:
        return True
    if not root:
        return False

    if head.val == root.val:
        if isSubPathMatch(head.next, root.right):
            return True

    return isSubPath(head, root.left) or isSubPath(head, root.right)

def isSubPathMatch(head, root):
    if not head:
        return True
    if not root:
        return False
    if head.val != root.val:
        return False
    return isSubPathMatch(head.next, root.right)

# Example usage
head = Node(1, Node(2, Node(3)))
root = TreeNode(1, TreeNode(2, TreeNode(1, None, TreeNode(3))), TreeNode(2, None, TreeNode(3)))

print(isSubPath(head, root))  # Output: True

Illustration:

In this example, the linked list

1->2->3

is a subtree of the binary tree. The function

isSubPath()

recursively explores the tree, starting from the root node, and calls

isSubPathMatch()

to check if the linked list matches the subtree rooted at the current node. In this case, the match is found starting from the node with value

1

.

Time and Space Complexity

Time Complexity: O(M * N), where M is the number of nodes in the linked list and N is the number of nodes in the binary tree. In the worst-case scenario, we might need to compare all nodes of the list with all nodes of the tree.
- Space Complexity: O(H), where H is the maximum height of the binary tree. This space is used for the recursive call stack. In the worst-case scenario, for a skewed tree, the height could be N (number of nodes in the tree).
  Key Points and Best Practices
Optimization: The code can be optimized by checking the presence of the first node of the linked list in the tree before proceeding with the full recursive search.
- Clarity: Use meaningful variable names and comments to improve code readability.
- Modularization: Break down complex tasks into smaller, reusable functions.
- Error Handling: Consider handling cases where either the linked list or the binary tree is empty.
  Conclusion
  This article explored the problem of determining if a linked list exists as a subtree within a binary tree. We discussed the key concepts, outlined a solution using depth-first search and recursive matching, and analyzed its time and space complexity. By understanding the differences between linked lists and binary trees, we were able to develop an efficient algorithm to solve this interesting problem.

1367. Linked List in Binary Tree