## 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;
}
```

**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.