Print path from root to a given node in a binary tree

Introduction

In this blog we will discuss the problem, i.e., " Print path from root to a given node in a binary tree,".It is highly asked in product-based companies. We'll go over all the steps of the solution.

Let's get started with the problem statement without further ado.

Prerequisites

Knowledge of trees and related terminologies such as recursion, trees, and the main traversals inorder, preorder, postorder are common prerequisites for every tree problem. It is not advisable to proceed to the Print path from root to a given node in a binary tree without mastering these fundamental methods and data structures.

Nonetheless, we'll try to go through every detail needed to Print path from root to a given node in a binary tree.

Problem Statement

Given a binary tree with different nodes (There are no two nodes with the same data values as the other node). Here the problem is to print the path from root to a given node n. If node n is absent, print "No Path is present for node n."

Sample Example

Example 1:

Input: 

n = 4

Output: 

Print path from root to a given node in a binary tree : root node to node 4
4->7->9

Example 2:

Input: 

n = 4

Output: 

Print path from root to a given node in a binary tree : root node to node 4
No Path is present from root node to node 4

Approach

Create a recursive function that searches the binary tree for the needed node by traversing the various paths. If node n is present, it returns true and accumulates the path nodes in some vector. Else it returns false.

Pseudocode

• If the root is NULL, return FALSE.
• If the root is not NULL, push the root's data into a vector for storing the path.
• if root->data = n, return TRUE.

• If node n is present in the root-> left or root-> right subtree, return TRUE.
• Else remove root-> data value from vector for storing the path.
• And return FALSE.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
class node
{
    public:
    int data;
    node* left;
    node* right;
};

node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return(Node);
}

bool Path_from_root_to_a_given_node(node *root, vector<int>& path, int n)
{
    // if root is NULL
    // there is no path
    if (!root)
       return false;
    

    path.push_back(root->data);

    if (root->data == n)
       return true;
    

    if (Path_from_root_to_a_given_node(root->left, path, n) ||
       Path_from_root_to_a_given_node(root->right, path, n))
       return true;
    
    
    path.pop_back();
    return false;        
}


int main()
{
    // binary tree formation
    node *root = newNode(4);
    root->left = newNode(5);
    root->right = newNode(7);
    root->left->right = newNode(1);
    root->left->right->left = newNode(8);
    root->left->right->right = newNode(2);
    root->right->left = newNode(9);
    root->right->right = newNode(6);
    root->right->left->right = newNode(3);

       
    int n = 9;
    cout<<"Print path from root to a given node in a binary tree : root node to node "<< n <<endl;
    vector<int> path;
    bool ans = Path_from_root_to_a_given_node(root, path, n);
       if (ans)
    {
       for (int i=0; i<path.size()-1; i++)
           cout << path[i] << "->";
       cout<<n<<endl;
    
    }
    
    // 'n' is not present in the binary tree
    else
       cout << "No Path is present from root node to node "<<n<<endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Print path from root to a given node in a binary tree : root node to node 9
4->7->9

Complexity Analysis

Time Complexity: o(n)

O(1) in the best case when the root node is the required node.

O(n)  in the worst case, where n is the number of nodes in the binary tree.

Space Complexity: o(n)

For storing the path from root node to node n.