Given root of the Binary Tree T and a linked list L, the task is to find the direction of path followed from root such that there exists a path from root to any leaf node of the Tree such that the values is that path forms the Linked List. If there doesn’t exist any such path then print “-1”.
Note: The path taken in the left direction is denoted by L and the path taken in the right direction is R.
Examples:
Input: LL = 1 -> 2 -> 5 -> 8
1
/ \
2 3
/ \ / \
4 5 6 8
/
8
Output: L R L
Explanation:
The path of linked list in binary tree is as follows:
1
/ \
2 3
/ \ / \
4 5 6 8
/
8Input: LL = 1 -> 2 -> 4
1
/ \
2 2
/ \ / \
4 5 6 8
/
8
Output: {L, L}
Approach: The given problem can be solved by traversing the binary tree and linked list simultaneously, if the current node doesn’t match with the current node of the linked list, then that path is incorrect. Otherwise, check for the other order for the valid paths. Follow the steps below to solve the given problem:
- Declare a function, say findPath(root, head, path) and perform the following steps in this function:
- If root is NULL or the root’s value is not the same as the head’s node value, then return false.
- If the current root node is the leaf node and head is the last node then return true.
- Insert the character ‘L’ in the vector path[] and recursively call for the left subtree as findPath(root->left, head->next, path) and if the value return by this function is true, then there exists a path and return true from the function. Otherwise, pop the last character from the vector path[].
- Insert the character ‘R’ in the vector path[] and recursively call for the right subtree as findPath(root->right, head->next, path) and if the value return by this function is true, then there exists a path and return true from the function. Otherwise, pop the last character from the vector path[].
- Otherwise, return false from the function.
- Initialize a vector, say path[] that stores the direction if Linked List is found in the given binary tree.
- Call for the function findPath(root, head, path).
- If the size of the vector path is 0, then print “-1”. Otherwise, print the path stored in the vector path[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; struct ListNode { int data; ListNode* next; ListNode( int data) { this ->data = data; this ->next = NULL; } }; struct TreeNode { TreeNode* left; TreeNode* right; int val; TreeNode( int x) : left(NULL), right(NULL), val(x) { } }; // Function to create the Linked list ListNode* makeList( int arr[], int n) { ListNode* h = NULL; ListNode* root; for ( int i = 0; i < n; i++) { int data = arr[i]; ListNode* node = new ListNode(data); if (h == NULL) { h = node; root = h; } else { root->next = node; root = node; } } return h; } // utility function to build tree // from its level order traversal TreeNode* build_tree( int nodes[], int n) { TreeNode* root = new TreeNode(nodes[0]); queue<TreeNode*> q; bool is_left = true ; TreeNode* cur = NULL; q.push(root); for ( int i = 1; i < n; i++) { TreeNode* node = NULL; if (nodes[i] != '#' ) { node = new TreeNode(nodes[i]); q.push(node); } if (is_left) { cur = q.front(); q.pop(); cur->left = node; is_left = false ; } else { cur->right = node; is_left = true ; } } return root; } // Function to find path of linked list // in binary tree, by traversing the // tree in pre-order fashion bool findPath(TreeNode* root, ListNode* head, vector< char >& path) { // Base Case if (root == NULL) { return false ; } // If current tree node is not same // as the current LL Node, then // return False if (root->val != head->data) return false ; // Complete the path of LL is traced if (root->left == NULL and root->right == NULL and head->next == NULL) { return true ; } // First go to left path.push_back( 'L' ); // If path found in left subtree if (findPath(root->left, head->next, path)) return true ; // Pop L because valid path is // not traced path.pop_back(); // Go to right path.push_back( 'R' ); // If path found in right subtree if (findPath(root->right, head->next, path)) return true ; // Pop R because valid path // is not traced path.pop_back(); return false ; } // Function to find the valid path void find(TreeNode* root, ListNode* head) { vector< char > path; // Function call to find the direction // of the LL path findPath(root, head, path); // If there doesn't exists any // such paths if (path.size() == 0) { cout << "-1" ; return ; } // Print the path for ( int i = 0; i < path.size(); i++) { cout << path[i] << " " ; } } // Driver Code int main() { int tree[] = { 1, 2, 3, 4, 5, 6, 8, -1, -1, 8 }; TreeNode* root = build_tree(tree, 10); int ll[] = { 1, 2, 5, 8 }; ListNode* head = makeList(ll, 4); find(root, head); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static class ListNode { int data; ListNode next; ListNode( int data) { this .data = data; this .next = null ; } }; static class TreeNode { TreeNode left; TreeNode right; int val; TreeNode( int x){ left = null ; right = null ; val = x; } }; // Function to create the Linked list static ListNode makeList( int arr[], int n) { ListNode h = null ; ListNode root = new ListNode( 0 ); for ( int i = 0 ; i < n; i++) { int data = arr[i]; ListNode node = new ListNode(data); if (h == null ) { h = node; root = h; } else { root.next = node; root = node; } } return h; } // utility function to build tree // from its level order traversal static TreeNode build_tree( int nodes[], int n) { TreeNode root = new TreeNode(nodes[ 0 ]); Queue<TreeNode> q = new LinkedList<>(); boolean is_left = true ; TreeNode cur = null ; q.add(root); for ( int i = 1 ; i < n; i++) { TreeNode node = null ; if (nodes[i] != 0 ) { node = new TreeNode(nodes[i]); q.add(node); } if (is_left) { cur = q.peek(); q.remove(); cur.left = node; is_left = false ; } else { cur.right = node; is_left = true ; } } return root; } // Function to find path of linked list // in binary tree, by traversing the // tree in pre-order fashion static boolean findPath(TreeNode root, ListNode head, Vector<Character> path) { // Base Case if (root == null ) { return false ; } // If current tree node is not same // as the current LL Node, then // return False if (root.val != head.data) return false ; // Complete the path of LL is traced if (root.left == null && root.right == null && head.next == null ) { return true ; } // First go to left path.add( 'L' ); // If path found in left subtree if (findPath(root.left, head.next, path)) return true ; // Pop L because valid path is // not traced path.remove(path.size()- 1 ); // Go to right path.add( 'R' ); // If path found in right subtree if (findPath(root.right, head.next, path)) return true ; // Pop R because valid path // is not traced path.remove(path.size()- 1 ); return false ; } // Function to find the valid path static void find(TreeNode root, ListNode head) { Vector<Character> path = new Vector<Character>(); // Function call to find the direction // of the LL path findPath(root, head, path); // If there doesn't exists any // such paths if (path.size() == 0 ) { System.out.print( "-1" ); return ; } // Print the path for ( int i = 0 ; i < path.size(); i++) { System.out.print(path.get(i)+ " " ); } } // Driver Code public static void main(String[] args) { int tree[] = { 1 , 2 , 3 , 4 , 5 , 6 , 8 , - 1 , - 1 , 8 }; TreeNode root = build_tree(tree, 10 ); int ll[] = { 1 , 2 , 5 , 8 }; ListNode head = makeList(ll, 4 ); find(root, head); } } // This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach from collections import deque class ListNode: def __init__( self , data): self .data = data self . next = None class TreeNode: def __init__( self , val): self .left = None self .right = None self .val = val def makeList(arr): h = None root = ListNode( 0 ) for i in range ( len (arr)): data = arr[i] node = ListNode(data) if h is None : h = node root = h else : root. next = node root = node return h def buildTree(nodes): root = TreeNode(nodes[ 0 ]) q = deque() is_left = True cur = None q.append(root) for i in range ( 1 , len (nodes)): node = None if nodes[i] ! = '#' : node = TreeNode(nodes[i]) q.append(node) if is_left: cur = q[ 0 ] q.popleft() cur.left = node is_left = False else : cur.right = node is_left = True return root def findPath(root, head, path): if root is None : return False if root.val ! = head.data: return False if root.left is None and root.right is None and head. next is None : return True path.append( 'L' ) if findPath(root.left, head. next , path): return True path.pop() path.append( 'R' ) if findPath(root.right, head. next , path): return True path.pop() return False def find(root, head): path = [] findPath(root, head, path) if len (path) = = 0 : print ( '-1' ) return for i in range ( len (path)): print (path[i], end = ' ' ) tree = [ 1 , 2 , 3 , 4 , 5 , 6 , 8 , - 1 , - 1 , 8 ] root = buildTree(tree) arr = [ 1 , 2 , 5 , 8 ] head = makeList(arr) find(root, head) # This code is contributed by Potta Lokesh |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ class ListNode { public int data; public ListNode next; public ListNode( int data) { this .data = data; this .next = null ; } }; class TreeNode { public TreeNode left; public TreeNode right; public int val; public TreeNode( int x){ left = null ; right = null ; val = x; } }; // Function to create the Linked list static ListNode makeList( int []arr, int n) { ListNode h = null ; ListNode root = new ListNode(0); for ( int i = 0; i < n; i++) { int data = arr[i]; ListNode node = new ListNode(data); if (h == null ) { h = node; root = h; } else { root.next = node; root = node; } } return h; } // utility function to build tree // from its level order traversal static TreeNode build_tree( int []nodes, int n) { TreeNode root = new TreeNode(nodes[0]); Queue<TreeNode> q = new Queue<TreeNode>(); bool is_left = true ; TreeNode cur = null ; q.Enqueue(root); for ( int i = 1; i < n; i++) { TreeNode node = null ; if (nodes[i] != 0) { node = new TreeNode(nodes[i]); q.Enqueue(node); } if (is_left) { cur = q.Peek(); q.Dequeue(); cur.left = node; is_left = false ; } else { cur.right = node; is_left = true ; } } return root; } // Function to find path of linked list // in binary tree, by traversing the // tree in pre-order fashion static bool findPath(TreeNode root, ListNode head, List< char > path) { // Base Case if (root == null ) { return false ; } // If current tree node is not same // as the current LL Node, then // return False if (root.val != head.data) return false ; // Complete the path of LL is traced if (root.left == null && root.right == null && head.next == null ) { return true ; } // First go to left path.Add( 'L' ); // If path found in left subtree if (findPath(root.left, head.next, path)) return true ; // Pop L because valid path is // not traced path.RemoveAt(path.Count-1); // Go to right path.Add( 'R' ); // If path found in right subtree if (findPath(root.right, head.next, path)) return true ; // Pop R because valid path // is not traced path.RemoveAt(path.Count-1); return false ; } // Function to find the valid path static void find(TreeNode root, ListNode head) { List< char > path = new List< char >(); // Function call to find the direction // of the LL path findPath(root, head, path); // If there doesn't exists any // such paths if (path.Count == 0) { Console.Write( "-1" ); return ; } // Print the path for ( int i = 0; i < path.Count; i++) { Console.Write(path[i]+ " " ); } } // Driver Code public static void Main(String[] args) { int []tree = { 1, 2, 3, 4, 5, 6, 8, -1, -1, 8 }; TreeNode root = build_tree(tree, 10); int []ll = { 1, 2, 5, 8 }; ListNode head = makeList(ll, 4); find(root, head); } } // This code is contributed by 29AjayKumar |
Javascript
// JavaScript code for the above approach class ListNode { constructor(data) { this .data = data; this .next = null ; } } class TreeNode { constructor(val) { this .left = null ; this .right = null ; this .val = val; } } let path = []; function makeList(arr) { let h = null ; let root = new ListNode(0); for (let i = 0; i < arr.length; i++) { let data = arr[i]; let node = new ListNode(data); if (h == null ) { h = node; root = h; } else { root.next = node; root = node; } } return h; } function buildTree(nodes) { let root = new TreeNode(nodes[0]); let q = []; let isLeft = true ; let cur = null ; q.push(root); for (let i = 1; i < nodes.length; i++) { let node = null ; if (nodes[i] !== 0) { node = new TreeNode(nodes[i]); q.push(node); } if (isLeft) { cur = q[0]; q.shift(); cur.left = node; isLeft = false ; } else { cur.right = node; isLeft = true ; } } return root; } function findPath(root, head) { if (root == null ) { return false ; } if (root.val !== head.data) { return false ; } if (root.left == null && root.right == null && head.next == null ) { return true ; } path.push( 'L' ); if (findPath(root.left, head.next)) { return true ; } path.pop(); path.push( 'R' ); if (findPath(root.right, head.next)) { return true ; } path.pop(); return false ; } function find(root, head) { findPath(root, head); if (path.length == 0) { console.log( '-1' ); return ; } for (let i = 0; i < path.length; i++) { console.log(path[i] + ' ' ); } } let tree = [1, 2, 3, 4, 5, 6, 8, -1, -1, 8]; let root = buildTree(tree); let arr = [1,2, 5, 8]; let head = makeList(arr); find(root, head); // This code is contributed by Potta Lokesh. |
L R L
Time Complexity: O(N + M), where N is number of nodes in Binary Tree and M is length of the Linked List.
Auxiliary Space: O(H), where H is the height of binary tree.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!