Given a root of the Binary Tree and head of the Linked List, the task is to check if all the elements of the linked list corresponds to a downward path from any node in the given Binary Tree.
Examples:
Input: Tree in the image below, list = {3, 6, 8}
Output: Yes
Explanation: There exists a downward path in the given Binary Tree, having all the elements of the linked list in the same order.Input: Tree in the image below, list = {1, 2, 5, 7}
Output: Yes
Approach: The given problem can be solved with the help of the DFS Traversal of the Binary tree. During the DFS traversal, if any node of the Binary Tree is equal to the head of the linked list, a recursive function isPathUntil() can be called to recursively check whether the other elements of the linked list also exist as a path from that node. If the complete linked list has been traversed, there exists a valid required path, hence return true. Otherwise, return false. Follow the steps below to solve the given problem:
- Declare a function, say isSubPathUtil(root, head) , and perform the following steps in this function:
- If the root is NULL, then return false.
- If the head is NULL, then return true.
- If the value of the current root node is the same as the value of the current head of LL, then recursively call for isSubPathUtil(root->left, head->next) and isSubPathUtil(root->right, head->next) and if the value returned one of these recursive calls is true, then return true. Otherwise, return false.
- Declare a function, say isSubPath(root, head), and perform the following steps in this function:
- If the root is NULL, then return false.
- If the head is NULL, then return true.
- If the value of the current root node is the same as the value of the current head of LL, then recursively call for isSubPath(root->left, head->next) and isSubPath(root->right, head->next) and if the value returned one of these recursive calls is true, then return true. Otherwise, return value call recursively for isSubPath(root->left, head) and isSubPath(root->right, head).
- After the above steps, if the value returned by the function isSubPath(root, head) is true , then print Yes . Otherwise, print No .
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;// Node of the Linked liststruct listNode { int val; struct listNode* next; // Constructor listNode(int data) { this->val = data; next = NULL; }};// Node of the Binary Search treestruct treeNode { int val; treeNode* right; treeNode* left; // Constructor treeNode(int data) { this->val = data; this->left = NULL; this->right = NULL; }};// Recursive function to check if there// exist a path from the node curTree// having the LL from the node curListbool isPathUtil(listNode* curList, treeNode* curTree){ // If the complete linked list // is traversed if (curList == NULL) return true; // If the tree node doesnot exist if (curTree == NULL) return false; if (curList->val == curTree->val) { // Recursively calling for the // next element return isPathUtil(curList->next, curTree->left) || isPathUtil(curList->next, curTree->right); } else { // If not found, return false return false; }}// Function to check if the linked list// exist as a downward path in Binary tree// using the DFS Traversal of the Treebool isPath(listNode* head, treeNode* root){ // If the current node of the // tree is Null if (root == NULL) return false; // If the complete linked list // has been found if (head == NULL) return true; // Stores if there exist the // required path bool isPossible = false; if (root->val == head->val) { // Recursively calling to // check the next node of // the linked list isPossible = isPathUtil( head->next, root->left) || isPathUtil( head->next, root->right); } // Recursive calling for the next // elements of the binary tree return isPossible || isPath(head, root->left) || isPath(head, root->right);}// Driver Codeint main(){ treeNode* root = new treeNode(1); root->left = new treeNode(2); root->right = new treeNode(3); root->left->left = new treeNode(4); root->left->right = new treeNode(5); root->left->right->left = new treeNode(7); root->right->right = new treeNode(6); root->right->right->left = new treeNode(8); root->right->right->right = new treeNode(9); listNode* head = new listNode(3); head->next = new listNode(6); head->next->next = new listNode(8); // Function Call cout << (isPath(head, root) ? "Yes" : "No"); return 0;} |
Java
// Java program for the above approach//include "bits/stdJava.h"import java.util.*;public class GFG{// Node of the Linked liststatic class listNode { int val; listNode next; // Constructor listNode(int data) { this.val = data; next = null; }};// Node of the Binary Search treestatic class treeNode { int val; treeNode right; treeNode left; // Constructor treeNode(int data) { this.val = data; this.left = null; this.right = null; }};// Recursive function to check if there// exist a path from the node curTree// having the LL from the node curListstatic boolean isPathUtil(listNode curList, treeNode curTree){ // If the complete linked list // is traversed if (curList == null) return true; // If the tree node doesnot exist if (curTree == null) return false; if (curList.val == curTree.val) { // Recursively calling for the // next element return isPathUtil(curList.next, curTree.left) || isPathUtil(curList.next, curTree.right); } else { // If not found, return false return false; }}// Function to check if the linked list// exist as a downward path in Binary tree// using the DFS Traversal of the Treestatic boolean isPath(listNode head, treeNode root){ // If the current node of the // tree is Null if (root == null) return false; // If the complete linked list // has been found if (head == null) return true; // Stores if there exist the // required path boolean isPossible = false; if (root.val == head.val) { // Recursively calling to // check the next node of // the linked list isPossible = isPathUtil( head.next, root.left) || isPathUtil( head.next, root.right); } // Recursive calling for the next // elements of the binary tree return isPossible || isPath(head, root.left) || isPath(head, root.right);}// Driver Codepublic static void main(String[] args){ treeNode root = new treeNode(1); root.left = new treeNode(2); root.right = new treeNode(3); root.left.left = new treeNode(4); root.left.right = new treeNode(5); root.left.right.left = new treeNode(7); root.right.right = new treeNode(6); root.right.right.left = new treeNode(8); root.right.right.right = new treeNode(9); listNode head = new listNode(3); head.next = new listNode(6); head.next.next = new listNode(8); // Function Call System.out.print((isPath(head, root) ? "Yes" : "No"));}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Node of the Linked listclass listNode: # Constructor def __init__ (self, data): self.val = data; self.next = None;# Node of the Binary Search treeclass treeNode: # Constructor def __init__ (self, data): self.val = data; self.left = None; self.right = None; # Recursive function to check if there# exist a path from the node curTree# having the LL from the node curListdef isPathUtil(curList, curTree): # If the complete linked list # is traversed if (curList == None): return True; # If the tree node doesnot exist if (curTree == None): return False; if (curList.val == curTree.val): # Recursively calling for the # next element return ( isPathUtil(curList.next, curTree.left) or isPathUtil(curList.next, curTree.right) ); else: # If not found, return false return False; # Function to check if the linked list# exist as a downward path in Binary tree# using the DFS Traversal of the Treedef isPath(head, root): # If the current node of the # tree is None if (root == None): return False; # If the complete linked list # has been found if (head == None): return True; # Stores if there exist the # required path isPossible = False; if (root.val == head.val): # Recursively calling to # check the next node of # the linked list isPossible = isPathUtil(head.next, root.left) or isPathUtil(head.next, root.right); # Recursive calling for the next # elements of the binary tree return isPossible or isPath(head, root.left) or isPath(head, root.right);# Driver Coderoot = treeNode(1);root.left = treeNode(2);root.right = treeNode(3);root.left.left = treeNode(4);root.left.right = treeNode(5);root.left.right.left = treeNode(7);root.right.right = treeNode(6);root.right.right.left = treeNode(8);root.right.right.right = treeNode(9);head = listNode(3);head.next = listNode(6);head.next.next = listNode(8);# Function Callprint( "Yes" if isPath(head, root) else "No");# This code is contributed by saurabh_jaiswal. |
C#
// C# program for the above approach//include "bits/stdJava.h"using System;public class GFG{// Node of the Linked listclass listNode { public int val; public listNode next; // Constructor public listNode(int data) { this.val = data; next = null; }};// Node of the Binary Search treeclass treeNode { public int val; public treeNode right; public treeNode left; // Constructor public treeNode(int data) { this.val = data; this.left = null; this.right = null; }};// Recursive function to check if there// exist a path from the node curTree// having the LL from the node curListstatic bool isPathUtil(listNode curList, treeNode curTree){ // If the complete linked list // is traversed if (curList == null) return true; // If the tree node doesnot exist if (curTree == null) return false; if (curList.val == curTree.val) { // Recursively calling for the // next element return isPathUtil(curList.next, curTree.left) || isPathUtil(curList.next, curTree.right); } else { // If not found, return false return false; }}// Function to check if the linked list// exist as a downward path in Binary tree// using the DFS Traversal of the Treestatic bool isPath(listNode head, treeNode root){ // If the current node of the // tree is Null if (root == null) return false; // If the complete linked list // has been found if (head == null) return true; // Stores if there exist the // required path bool isPossible = false; if (root.val == head.val) { // Recursively calling to // check the next node of // the linked list isPossible = isPathUtil( head.next, root.left) || isPathUtil( head.next, root.right); } // Recursive calling for the next // elements of the binary tree return isPossible || isPath(head, root.left) || isPath(head, root.right);}// Driver Codepublic static void Main(String[] args){ treeNode root = new treeNode(1); root.left = new treeNode(2); root.right = new treeNode(3); root.left.left = new treeNode(4); root.left.right = new treeNode(5); root.left.right.left = new treeNode(7); root.right.right = new treeNode(6); root.right.right.left = new treeNode(8); root.right.right.right = new treeNode(9); listNode head = new listNode(3); head.next = new listNode(6); head.next.next = new listNode(8); // Function Call Console.Write((isPath(head, root) ? "Yes" : "No"));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Node of the Linked listclass listNode{ // Constructor constructor(data) { this.val = data; this.next = null; }}// Node of the Binary Search treeclass treeNode{ // Constructor constructor(data) { this.val = data; this.left = null; this.right = null; }}// Recursive function to check if there// exist a path from the node curTree// having the LL from the node curListfunction isPathUtil(curList, curTree) { // If the complete linked list // is traversed if (curList == null) return true; // If the tree node doesnot exist if (curTree == null) return false; if (curList.val == curTree.val) { // Recursively calling for the // next element return ( isPathUtil(curList.next, curTree.left) || isPathUtil(curList.next, curTree.right) ); } else { // If not found, return false return false; }}// Function to check if the linked list// exist as a downward path in Binary tree// using the DFS Traversal of the Treefunction isPath(head, root){ // If the current node of the // tree is null if (root == null) return false; // If the complete linked list // has been found if (head == null) return true; // Stores if there exist the // required path let isPossible = false; if (root.val == head.val) { // Recursively calling to // check the next node of // the linked list isPossible = isPathUtil(head.next, root.left) || isPathUtil(head.next, root.right); } // Recursive calling for the next // elements of the binary tree return isPossible || isPath(head, root.left) || isPath(head, root.right);}// Driver Codelet root = new treeNode(1);root.left = new treeNode(2);root.right = new treeNode(3);root.left.left = new treeNode(4);root.left.right = new treeNode(5);root.left.right.left = new treeNode(7);root.right.right = new treeNode(6);root.right.right.left = new treeNode(8);root.right.right.right = new treeNode(9);let head = new listNode(3);head.next = new listNode(6);head.next.next = new listNode(8);// Function Calldocument.write(isPath(head, root) ? "Yes" : "No");// This code is contributed by saurabh_jaiswal.</script> |
Output:
Yes
Time Complexity: O(N * M) where N = Number of nodes in the Binary Tree and M = Number of nodes in the Linked list.
Auxiliary Space: O(height of the tree)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
