Check if there is a root to leaf path with given sequence

Last Updated : 11 Sep, 2023

Given a binary tree and an array, the task is to find if the given array sequence is present as a root-to-leaf path in given tree.

Examples :

Input : arr[] = {5, 2, 4, 8} for above tree
Output: "Path Exist"

Input :  arr[] = {5, 3, 4, 9} for above tree
Output: "Path does not Exist"

A simple solution for this problem is to find all root-to-leaf paths in given tree and for each root-to-leaf path check whether path and given sequence in array both are identical or not.

An efficient solution for this problem is to traverse the tree once and while traversing the tree we have to check if path from root to current node is identical to the given sequence of root to leaf path.

Algorithm:

Start traversing tree in preorder fashion.

Whenever we moves down in tree then we also move by one index in given sequence of root to leaf path .

If current node is equal to the arr[index] this means that till this level of tree path is identical.

Now remaining path will either be in left subtree or in right subtree.

If any node gets mismatched with arr[index] this means that current path is not identical to the given sequence of root to leaf path, so we return back and move in right subtree.

Now when we are at leaf node and it is equal to arr[index] and there is no further element in given sequence of root to leaf path, this means that path exist in given tree.

C++

// C++ program to see if there is a root to leaf path 
// with given sequence. 
#include<bits/stdc++.h> 
using namespace std; 
  
/* A binary tree node has data, pointer to left child 
and a pointer to right child */
struct Node 
{ 
    int data; 
    struct Node* left, *right; 
}; 
  
/* utility that allocates a new node with the 
given data and NULL left and right pointers. */
struct Node* newnode(int data) 
{ 
    struct Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 
  
  
// Util function 
bool existPathUtil(struct Node *root, int arr[], int n, int index) 
{ 
    // If root is NULL or reached end of the array 
    if(root == NULL or index==n)  
            return false;  
  
    // If current node is leaf 
    if (root->left == NULL && root->right == NULL) 
    { 
        if((root->data == arr[index]) && (index == n-1))  
            return true;  
         
       return false; 
    }  
  
    // If current node is equal to arr[index] this means 
    // that till this level path has been matched and 
    // remaining path can be either in left subtree or 
    // right subtree. 
    return ((index < n) && (root->data == arr[index]) && 
                (existPathUtil(root->left, arr, n, index+1) || 
                existPathUtil(root->right, arr, n, index+1) )); 
} 
  
// Function to check given sequence of root to leaf path exist 
// in tree or not. 
// index represents current element in sequence of rooth to 
// leaf path 
bool existPath(struct Node *root, int arr[], int n, int index) 
{ 
    if(!root) 
        return (n==0); 
          
    return existPathUtil(root, arr, n, 0); 
} 
  
// Driver function to run the case 
int main() 
{ 
    // arr[] --> sequence of root to leaf path 
    int arr[] = {5, 8, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    struct Node *root = newnode(5); 
    root->left = newnode(3); 
    root->right = newnode(8); 
    root->left->left = newnode(2); 
    root->left->right = newnode(4); 
    root->left->left->left = newnode(1); 
    root->right->left = newnode(6); 
    root->right->left->right = newnode(7); 
  
    existPath(root, arr, n, 0)? cout << "Path Exists" : 
                                cout << "Path does not Exist"; 
    return 0; 
} 

Java

// Java program to see if there is a root to leaf path 
// with given sequence. 
import java.io.*; 
  
class Node 
{ 
    int data; 
    Node left; 
    Node right; 
      
    Node(int data) 
    { 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
} 
  
  
class GFG { 
      
    // Util function 
    static boolean existPathUtil(Node root, int arr[],  
                        int n, int index) 
    { 
        // If root is NULL or  
        // reached end of the array 
        if(root == null || index==n)  
                return false;  
       
        // If current node is leaf 
        if (root.left == null &&  
                        root.right == null) 
        { 
            if((root.data == arr[index]) &&  
                                (index == n-1))  
                return true;  
              
           return false; 
        }  
       
        // If current node is equal to arr[index] this means 
        // that till this level path has been matched and 
        // remaining path can be either in left subtree or 
        // right subtree. 
        return ((index < n) && (root.data == arr[index])  
            &&  (existPathUtil(root.left, arr, n, index+1) 
            || existPathUtil(root.right, arr, n, index+1) )); 
    } 
       
    // Function to check given sequence of root  
    // to leaf path exist in tree or not. 
    // index : current element in sequence of root to 
    // leaf path 
    static boolean existPath(Node root, int arr[],  
                                    int n, int index) 
    { 
        if(root == null) 
            return (n==0); 
               
        return existPathUtil(root, arr, n, 0); 
    } 
  
      
    public static void main (String[] args) { 
          
    // arr[] : sequence of root to leaf path 
    int arr[] = {5, 8, 6, 7}; 
    int n = arr.length; 
    Node root = new Node(5); 
    root.left = new Node(3); 
    root.right = new Node(8); 
    root.left.left = new Node(2); 
    root.left.right = new Node(4); 
    root.left.left.left = new Node(1); 
    root.right.left = new Node(6); 
    root.right.left.right = new Node(7); 
   
    if(existPath(root, arr, n, 0)) 
        System.out.println("Path Exists"); 
    else
        System.out.println("Path does not Exist"); 
          
    } 
} 

Python3

# Python program to see if 
# there is a root to leaf path 
# with given sequence 
  
# Class of Node 
class Node: 
      
    # Constructor to create a  
    # node in Binary Tree 
    def __init__(self, val): 
        self.val = val 
        self.left = None
        self.right = None
   
# Util function    
def existPathUtil(root, arr, n, index): 
      
    # If root is NULL or reached  
    # end of the array 
    if not root or index == n: 
        return False
      
    # If current node is leaf 
    if not root.left and not root.right: 
        if root.val == arr[index] and index == n-1: 
            return True
        return False
      
    # If current node is equal to arr[index] this means 
    # that till this level path has been matched and 
    # remaining path can be either in left subtree or 
    # right subtree. 
    return ((index < n) and (root.val == arr[index]) and \ 
            (existPathUtil(root.left, arr, n, index+1) or \ 
            existPathUtil(root.right, arr, n, index+1))) 
  
# Function to check given sequence of root to leaf path exist 
# in tree or not. 
# index represents current element in sequence of rooth to 
# leaf path          
def existPath(root, arr, n, index): 
    if not root: 
        return (n == 0) 
          
    return existPathUtil(root, arr, n, 0) 
  
# Driver Code 
if __name__ == "__main__": 
    arr = [5, 8, 6, 7] 
    n = len(arr) 
    root = Node(5) 
    root.left = Node(3) 
    root.right = Node(8) 
    root.left.left = Node(2) 
    root.left.right = Node(4) 
    root.left.left.left = Node(1) 
    root.right.left = Node(6) 
    root.right.left.right = Node(7) 
      
    if existPath(root, arr, n, 0): 
        print("Path Exists") 
    else: 
        print("Path does not Exist") 

C#

// C# program to see if there 
// is a root to leaf path  
// with given sequence.  
using System; 
  
public class CheckForPath  
{ 
  
    // function to check given sequence 
    // of root to leaf path exist  
    // in tree or not.  
    // index represents current element 
    // in sequence of rooth to  
    // leaf path  
    public static bool existPath(Node root, 
                        int []arr, int index) 
    { 
        // If root is NULL, then there 
        // must not be any element  
        // in array.  
        if(root == null) 
        { 
            return arr.Length == 0; 
        } 
  
        // If this node is a leaf and matches with last entry  
        // of array.  
        if((root.left == null && root.right == null) &&  
                                (root.data == arr[index] && 
                                root.data == arr[arr.Length - 1])) 
        { 
            return true; 
        } 
  
        // If current node is equal to arr[index] this means  
        // that till this level path has been matched and  
        // remaining path can be either in left subtree or  
        // right subtree.  
        return (index < arr.Length && (root.data == arr[index] &&  
                       (existPath(root.left,arr,index + 1) ||  
                        existPath(root.right, arr, index + 1)))); 
    } 
      
    // Driver code 
    public static void Main()  
    { 
        // arr[] is sequence of root to leaf path  
        int []arr = {5, 8, 6, 7};  
        Node root=new Node(5); 
        root.left=new Node(3); 
        root.right=new Node(8); 
        root.left.left = new Node(2);  
        root.left.right = new Node(4);  
        root.left.left.left = new Node(1);  
        root.right.left = new Node(6);  
        root.right.left.right = new Node(7);  
  
        if(existPath(root, arr, 0)) 
        { 
            Console.Write("Path Exists"); 
        } 
        else
        { 
            Console.Write("Path does not Exist"); 
        } 
    }  
} 
  
/* A binary tree node has data,  
pointer to left child and a 
pointer to right child */
public class Node  
{  
    public int data;  
    public Node left, right;  
    public Node(int data) 
    { 
        this.data = data; 
        left = right = null; 
    } 
}; 
  
// This code is contributed Rajput-Ji  

Javascript

// JavaScript program to see if there is a root to leaf path 
// with given sequence. 
  
class Node { 
    constructor(data) { 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
} 
  
// Utility function 
function existPathUtil(root, arr, n, index) { 
    // If root is NULL or reached end of the array 
    if (!root || index === n) return false; 
  
    // If current node is leaf 
    if (root.left === null && root.right === null) { 
        if (root.data === arr[index] && index === n - 1) return true; 
  
        return false; 
    } 
  
    // If current node is equal to arr[index] this means 
    // that till this level path has been matched and 
    // remaining path can be either in left subtree or 
    // right subtree. 
    return ( 
        index < n && 
        root.data === arr[index] && 
        (existPathUtil(root.left, arr, n, index + 1) || 
            existPathUtil(root.right, arr, n, index + 1)) 
    ); 
} 
  
// Function to check given sequence of root to leaf path exist 
// in tree or not. 
// index represents current element in sequence of rooth to 
// leaf path 
function existPath(root, arr, n, index) { 
    if (!root) return n === 0; 
  
    return existPathUtil(root, arr, n, 0); 
} 
  
// Driver function to run the case 
// arr[] --> sequence of root to leaf path 
let arr = [5, 8, 6, 7]; 
let n = arr.length; 
let root = new Node(5); 
root.left = new Node(3); 
root.right = new Node(8); 
root.left.left = new Node(2); 
root.left.right = new Node(4); 
root.left.left.left = new Node(1); 
root.right.left = new Node(6); 
root.right.left.right = new Node(7); 
  
existPath(root, arr, n, 0) 
    ? console.log("Path Exists") 
    : console.log("Path does not Exist"); 
  
// This code is contributed by adityamaharshi21

Output

Path Exists

Time Complexity: O(N), the time complexity of this algorithm is O(N), where N is the number of nodes in the tree.
Auxiliary Space: O(h), where h is the height of the tree, this space is due to the recursive call stack.

Shashank Mishra ( Gullu )

Improve

Convert Ternary Expression to a Binary Tree

Remove all nodes which don't lie in any path with sum>= k

Types of Binary Tree

Some important Binary tree traversals

Easy problems on Binary Tree

Intermediate problems on Binary Tree

Hard problems on Binary Tree

Check if there is a root to leaf path with given sequence

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?