Java Algorithms: Linked List in Binary Tree (LeetCode)

Task description:

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.

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: Nodes in blue form a subpath in the binary Tree.

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

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: There is no path in the binary tree that contains all the elements of the linked list from head.

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 for each node in the linked list and binary tree.

Reasoning:

Seems like this task forces us to used at least 2 different data structures, binary tree, and linked list. Let’s introduce 2 simple classes to describe essential pieces which make binary tree and linked list.

https://gist.github.com/RakhmedovRS/94bf17787d3873117997e9d3fa0a23e1

https://gist.github.com/RakhmedovRS/3c97726e4aa77734d817947131b7696a

You might notice some similarities between them. The only difference is that TreeNode has an additional pointer and that is all. In fact, you can represent some types of BinaryTrees using LinkedLists

Let’s have some fun and change our “angle of view”. The same thing can be done with the second example.

Let’s get back to our task. We need to find out if a given binary tree contains a linked list in one of its paths starting from any node. Don’t be scared by the task definition it’s easier than you think.

Let’s talk about the brute force solution. What we can do is iterate through every node of the binary tree and starting from it iterate through the linked list. If we iterate through every node in the binary tree it’ll be O(n) — linear time complexity. Iteration over every node in the linked list will be O(n) as well. If for each node of the binary tree we iterate over the linked list it’ll give us O(n²) — quadratic time complexity.

Sounds like a bad solution? Let’s have a look at provided numbers. The maximum number of nodes in a binary tree is 2500. The maximum number of nodes in the linked list is 100. 2500 * 100 = 250'000 maximum number of operations we will have to perform in order to solve the problem. Any modern CPU can process up to 10⁸ operation in less than one second. Our brute force solution has 2*10⁵.

Solution:

I’m going to implement the solution using a recursive approach, but it also can be solved non-recursively.

In the isSubPath method we call recursive method traverse

https://gist.github.com/RakhmedovRS/4fcfe3c046099ab3a1362854b36ec3e5

In traverse function we check if current root node if null and as a result we return whether or not head is equal to null. If values in a node in binary tree and in a node in linked list are equals, we can try to verify if we found a match. To do it we call findPath method.

Otherwise we continue exploring the binary tree by going to the left and right nodes.

https://gist.github.com/RakhmedovRS/bbe2bc542f73aea6d7ec035fa5313de3

In findPath method we do almost the same thing we did in traverse. If head is null means we reached the end of the linked list and we return true. If root is null means we explored all nodes in a binary tree and we cannot continue. We return false. In all other cases we check equality of values in nodes of a binary tree and a linked list. At the same time we try to explore both paths from the current node of binary tree, we try to go to the left child and right one. Any of available paths will be sufficient for us to answer the main question — binary tree contains all nodes in provided linked list.

https://gist.github.com/RakhmedovRS/e9a1695b8e14c2de165fa36489a4b454

The full solution

https://gist.github.com/RakhmedovRS/db8111d9d89a0ba2d910f5ef37036290

As a mentioned previously this solution has quadratic time complexity but it’s fine because we know exact restrictions for the task. Testing system proves it.