Introduction
Do you know how we can check if all the elements of a linked list corresponds to a downward path from any node in the binary tree? If not, then don’t worry. We will clear all your doubts and make you understand how we can solve the same.
A linked list in a binary tree contains a sequence of nodes where each node has a pointer to the next node in a series. This sequence is embedded in the binary tree. One usage of a linked list in binary trees is the representation of a sequence of nodes that follow a specific order within a tree.
Problem statement
Check if all elements of given Linked List corresponds to a downward path from any node in given Binary Tree.
In the problem statement, we are given a head of a linked list and the root of a binary tree. Our task is to check whether the linked list elements are present in the binary tree, i.e., if they correspond to any downward path in the tree. Downward path refers to a path that starts at some node and goes downwards.
Example
Input
head=[3,5,6]
root=[1,4,3, null,2,5, null,9, null,6,8, null, null, null, null,1,7]Output
true
Approach
We need to find the presence of the given linked list in the given tree. To do so, we must need to traverse the binary tree. We can traverse the tree using BFS or DFS Algorithm. Both techniques are acceptable. Moving forward, we will solve this problem using the DFS approach.
DFS (Depth First Search) Approach
During DFS, we can use a recursive approach where we have to start from the root of the binary tree and compare it with the head of the linked list. If we get a match, we can recursively check the left and right children of the root node with the next node in the linked list. But if we don't get a match, we can return false. And if we reach the end of the linked list and all the nodes are matched with some of the downward paths, we can return true.
The pseudo-code of the above approach is as follows:
function NinjaPath(head, root){
//check for base cases
if (head==NULL) return true;
if (node==NULL) return false; //if no binary tree; then no path will be available
//simply calls the dfs function with root and head as arguments
return dfs(root, head);
}
function dfs(node, head){
if (head==NULL) return true;
if (node==NULL) return false; //if no binary tree; then no path will be available
if (node->val==head->val){
//if a match found
//recursively checks for the children nodes as well
//if path found return true
if(dfs(node->left, head->next) or dfs(node->right, head->next)){
return true;
}
}
//if no match
//the function is called on its left and right children of current node
//with the same node in linked list
return dfs(node->left, head) or dfs(node->right, head)
}
Below is the C++ implementation:
#include "bits/stdc++.h"
using namespace std;
// Node of the Binary Search tree
struct NinjaTreeNode {
int val;
NinjaTreeNode* left;
NinjaTreeNode* right;
};
//Linked List Node
struct NinjaListNode {
int val;
struct NinjaListNode* next;
// Constructor
NinjaListNode(int data)
{
this->val = data;
next = NULL;
}
};
bool dfs(NinjaListNode* node, NinjaTreeNode* root) {
if (!node) {
return true;
}
if (!root) {
return false;
}
if (node->val != root->val) {
return false;
}
return dfs(node->next, root->left) || dfs(node->next, root->right);
}
// Recursive function to check if there exist a downward path or not.
bool NinjaPath(NinjaListNode* head, NinjaTreeNode* root) {
if (!head) {
return true;
}
if (!root) {
return false;
}
if (dfs(head, root)) {
return true;
}
return NinjaPath(head, root->left) || NinjaPath(head, root->right);
}
int main()
{
NinjaTreeNode* root = new NinjaTreeNode{1,
// left subtree
new NinjaTreeNode{4, nullptr,
new NinjaTreeNode{2, new NinjaTreeNode{9, nullptr, nullptr}, nullptr}
},
// right subtree
new NinjaTreeNode{3, new NinjaTreeNode{5,
new NinjaTreeNode{6, nullptr, nullptr},
new NinjaTreeNode{8, new NinjaTreeNode{1, nullptr, nullptr}, new
NinjaTreeNode{7, nullptr, nullptr}}}, nullptr}
};
//Linked List
NinjaListNode* head = new NinjaListNode(3);
head->next = new NinjaListNode(5);
head->next->next = new NinjaListNode(6);
if((NinjaPath(head, root))){
cout <<"Linked list found in Binary Tree." ;
}
else{
cout <<"Linked list not found in Binary Tree." ;
}
return 0;
}
Output
Explanation
In the above code, we have made a structure named NinjaListNode, which is creating a linked list node. And, similarly we have made a structure named NinjaTreeNode, which is creating a binary tree node. We have made a recursive function named ‘NinjaPath()’ that takes the head of the linked list and the root of the binary tree as input arguments. It calls a dfs function. This function will return true if the linked list corresponds to some downward path in the binary tree. The ‘dfs()’ function will check if the given node of the linked list matches with a node in a binary tree or not. Similarly, recursively we can check the children of the binary tree node with the next node in the linked list. The ‘dfs()’ function will call itself recursively, with the left and right children of the binary tree node, till it reaches the end of the linked list.
Time Complexity
-
The time complexity of the depth-first-search approach is O(n*m).
-
Here, n represents the number of nodes in the binary tree, whereas m is the length of the linked list.
-
We got this as time complexity as the dfs function is called once for each node in the binary tree, so for each call, it will compare the current node in the binary tree to the present node in the linked list. Also, it will recursively call itself on left and right children.
-
In the worst-case scenario, the linked list will be traversed from the beginning for each current node in the binary tree.
Space Complexity
-
The space complexity will be O(h+m).
-
Here, h is the height of the binary tree, and m refers to the length of the linked list. The dfs function will maintain a recursive call stack that contains the maximum depth h, i.e., the height of the binary tree.
A reference to the current node in the linked list will also be maintained, which will take up additional ‘m’ space in the worst-case scenario, i.e., when the linked list is longer than the height of the binary tree.
19+ registered 
