Task description: Given a binary tree and a linked list with as the first node. root head Return True if all the elements in the linked list starting from the correspond to some connected in the binary tree otherwise return False. head downward path 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] for each node in the linked list and binary tree. 1 <= Node.val <= 100 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 method we call recursive method isSubPath 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 method. findPath Otherwise we continue exploring the binary tree by going to the left and right nodes. https://gist.github.com/RakhmedovRS/bbe2bc542f73aea6d7ec035fa5313de3 In method we do almost the same thing we did in . 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. findPath traverse 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.

Different

Implementing a Singly or Doubly Linked List in Java (A LeetCode Question)

Java Algorithms: Merge k Sorted Lists (LeetCode)

Java Algorithms: Linked List in Binary Tree (LeetCode)

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Clone Graph Blind75 LeetCode Problem

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Clone Graph Blind75 LeetCode Problem

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps