Java Algorithms: Linked List in Binary Tree (LeetCode) by@rakhmedovrs

Java Algorithms: Linked List in Binary Tree (LeetCode)

July 9th 2022 17,347 reads

Trending #10

Read on Terminal Reader
Open TLDR
react to story with heart
react to story with light
react to story with boat
react to story with money
The number of nodes in the tree will be in the range `[1, 2500]` For each node in the linked list and binary tree. The maximum of the number of node in a binary tree is 2500 nodes in a linked list. The only difference is that TreeTree has an additional pointer and that is all. In fact, you can represent some types of BinaryTrees using LinkedLists using the same pointer. We need to find out if a given binary tree contains a given. binary tree containing a. linked list starting from the. head. If all the elements in the. linked. list from the `head` correspond to some *downward path* connected in the binary tree otherwise return False.
image
Ruslan Rakhmedov HackerNoon profile picture

Ruslan Rakhmedov

Software Engineer, Stripe

github social iconlinkedin social icon


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:

image

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:

image

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.




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

First example of BinaryTree which can be represented by LinkedList

First example of BinaryTree which can be represented by LinkedList



Second example of BinaryTree which can be represented by LinkedList

Second example of BinaryTree which can be represented by LinkedList


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


First example rotated to the left

First example rotated to the left


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


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.


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.


The full solution


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.

image



react to story with heart
react to story with light
react to story with boat
react to story with money
L O A D I N G
. . . comments & more!