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

Given a binary tree with distinct nodes(no two nodes have the same have data values). The problem is to print the path from root to a given node x. If node x is not present then print “No Path”.

Examples:

```Input :          1
/
2     3
/    /
4   5  6   7

x = 5

Output : 1->2->5
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Create a recursive function that traverses the different path in the binary tree to find the required node x. If node x is present then it returns true and accumulates the path nodes in some array arr[]. Else it returns false.

Following are the cases during the traversal:

1. If root = NULL, return false.
2. push the root’s data into arr[].
3. if root’s data = x, return true.
4. if node x is present in root’s left or right subtree, return true.
5. Else remove root’s data value from arr[] and return false.

This recursive function can be accessed from other function to check whether node x is present or not and if it is present, then the path nodes can be accessed from arr[]. You can define arr[] globally or pass its reference to the recursive function.

## C++

 `// C++ implementation to print the path from root ` `// to a given node in a binary tree ` `#include ` `using` `namespace` `std; ` ` `  `// structure of a node of binary tree ` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``Node *left, *right; ` `}; ` ` `  `/* Helper function that allocates a new node with the ` `   ``given data and NULL left and right pointers. */` `struct` `Node* getNode(``int` `data) ` `{ ` `    ``struct` `Node *newNode = ``new` `Node; ` `    ``newNode->data = data; ` `    ``newNode->left = newNode->right = NULL; ` `    ``return` `newNode; ` `} ` ` `  `// Returns true if there is a path from root ` `// to the given node. It also populates  ` `// 'arr' with the given path ` `bool` `hasPath(Node *root, vector<``int``>& arr, ``int` `x) ` `{ ` `    ``// if root is NULL ` `    ``// there is no path ` `    ``if` `(!root) ` `        ``return` `false``; ` `     `  `    ``// push the node's value in 'arr' ` `    ``arr.push_back(root->data);     ` `     `  `    ``// if it is the required node ` `    ``// return true ` `    ``if` `(root->data == x)     ` `        ``return` `true``; ` `     `  `    ``// else check whether the required node lies ` `    ``// in the left subtree or right subtree of  ` `    ``// the current node ` `    ``if` `(hasPath(root->left, arr, x) || ` `        ``hasPath(root->right, arr, x)) ` `        ``return` `true``; ` `     `  `    ``// required node does not lie either in the  ` `    ``// left or right subtree of the current node ` `    ``// Thus, remove current node's value from  ` `    ``// 'arr'and then return false     ` `    ``arr.pop_back(); ` `    ``return` `false``;             ` `} ` ` `  `// function to print the path from root to the ` `// given node if the node lies in the binary tree ` `void` `printPath(Node *root, ``int` `x) ` `{ ` `    ``// vector to store the path ` `    ``vector<``int``> arr; ` `     `  `    ``// if required node 'x' is present ` `    ``// then print the path ` `    ``if` `(hasPath(root, arr, x)) ` `    ``{ ` `        ``for` `(``int` `i=0; i"``; ` `        ``cout << arr[arr.size() - 1];     ` `    ``} ` `     `  `    ``// 'x' is not present in the binary tree  ` `    ``else` `        ``cout << ``"No Path"``; ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``// binary tree formation ` `    ``struct` `Node *root = getNode(1); ` `    ``root->left = getNode(2); ` `    ``root->right = getNode(3); ` `    ``root->left->left = getNode(4); ` `    ``root->left->right = getNode(5); ` `    ``root->right->left = getNode(6); ` `    ``root->right->right = getNode(7); ` `         `  `    ``int` `x = 5; ` `    ``printPath(root, x); ` `    ``return` `0; ` `}  `

## Java

 `// Java implementation to print the path from root  ` `// to a given node in a binary tree  ` `import` `java.util.ArrayList; ` `public` `class` `PrintPath { ` ` `  `    ``// Returns true if there is a path from root  ` `    ``// to the given node. It also populates   ` `    ``// 'arr' with the given path  ` `    ``public` `static` `boolean` `hasPath(Node root, ArrayList arr, ``int` `x)  ` `    ``{  ` `        ``// if root is NULL  ` `        ``// there is no path  ` `        ``if` `(root==``null``)  ` `            ``return` `false``;  ` `       `  `        ``// push the node's value in 'arr'  ` `        ``arr.add(root.data);      ` `       `  `        ``// if it is the required node  ` `        ``// return true  ` `        ``if` `(root.data == x)      ` `            ``return` `true``;  ` `       `  `        ``// else check whether the required node lies  ` `        ``// in the left subtree or right subtree of   ` `        ``// the current node  ` `        ``if` `(hasPath(root.left, arr, x) ||  ` `            ``hasPath(root.right, arr, x))  ` `            ``return` `true``;  ` `       `  `        ``// required node does not lie either in the   ` `        ``// left or right subtree of the current node  ` `        ``// Thus, remove current node's value from   ` `        ``// 'arr'and then return false      ` `        ``arr.remove(arr.size()-``1``);  ` `        ``return` `false``;              ` `    ``}  ` ` `  `    ``// function to print the path from root to the  ` `    ``// given node if the node lies in the binary tree  ` `    ``public` `static` `void` `printPath(Node root, ``int` `x)  ` `    ``{  ` `        ``// ArrayList to store the path  ` `        ``ArrayList arr=``new` `ArrayList<>(); ` `     `  `        ``// if required node 'x' is present  ` `        ``// then print the path  ` `        ``if` `(hasPath(root, arr, x))  ` `        ``{  ` `            ``for` `(``int` `i=``0``; i"``); ` `            ``System.out.print(arr.get(arr.size() - ``1``));     ` `        ``}  ` `       `  `        ``// 'x' is not present in the binary tree   ` `        ``else` `            ``System.out.print(``"No Path"``);  ` `    ``}  ` ` `  `    ``public` `static` `void` `main(String args[]) { ` `        ``Node root=``new` `Node(``1``); ` `        ``root.left = ``new` `Node(``2``);  ` `        ``root.right = ``new` `Node(``3``);  ` `        ``root.left.left = ``new` `Node(``4``);  ` `        ``root.left.right = ``new` `Node(``5``);  ` `        ``root.right.left = ``new` `Node(``6``);  ` `        ``root.right.right = ``new` `Node(``7``);  ` `        ``int` `x=``5``; ` `        ``printPath(root, x); ` `    ``} ` `} ` ` `  `// A node of binary tree  ` `class` `Node  ` `{  ` `    ``int` `data;  ` `    ``Node left, right;  ` `    ``Node(``int` `data) ` `    ``{ ` `        ``this``.data=data; ` `        ``left=right=``null``; ` `    ``} ` `};  ` `//This code is contributed by Gaurav Tiwari `

## Python3

 `# Python3 implementation to prthe path from  ` `# root to a given node in a binary tree  ` ` `  `# Helper Class that allocates a new node  ` `# with the given data and None left and  ` `# right pointers.  ` `class` `getNode: ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data  ` `        ``self``.left ``=` `self``.right ``=` `None` ` `  `# Returns true if there is a path from  ` `# root to the given node. It also  ` `# populates 'arr' with the given path  ` `def` `hasPath(root, arr, x): ` `     `  `    ``# if root is None there is no path  ` `    ``if` `(``not` `root): ` `        ``return` `False` `     `  `    ``# push the node's value in 'arr'  ` `    ``arr.append(root.data)      ` `     `  `    ``# if it is the required node  ` `    ``# return true  ` `    ``if` `(root.data ``=``=` `x):      ` `        ``return` `True` `     `  `    ``# else check whether the required node  ` `    ``# lies in the left subtree or right  ` `    ``# subtree of the current node  ` `    ``if` `(hasPath(root.left, arr, x) ``or`  `        ``hasPath(root.right, arr, x)):  ` `        ``return` `True` `     `  `    ``# required node does not lie either in  ` `    ``# the left or right subtree of the current  ` `    ``# node. Thus, remove current node's value   ` `    ``# from 'arr'and then return false      ` `    ``arr.pop(``-``1``)  ` `    ``return` `False` ` `  `# function to prthe path from root to  ` `# the given node if the node lies in ` `# the binary tree  ` `def` `printPath(root, x): ` `     `  `    ``# vector to store the path  ` `    ``arr ``=` `[]  ` `     `  `    ``# if required node 'x' is present  ` `    ``# then prthe path  ` `    ``if` `(hasPath(root, arr, x)): ` `        ``for` `i ``in` `range``(``len``(arr) ``-` `1``): ` `            ``print``(arr[i], end ``=` `"->"``)  ` `        ``print``(arr[``len``(arr) ``-` `1``]) ` `     `  `    ``# 'x' is not present in the  ` `    ``# binary tree  ` `    ``else``: ` `        ``print``(``"No Path"``) ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` `     `  `    ``# binary tree formation  ` `    ``root ``=` `getNode(``1``)  ` `    ``root.left ``=` `getNode(``2``)  ` `    ``root.right ``=` `getNode(``3``)  ` `    ``root.left.left ``=` `getNode(``4``)  ` `    ``root.left.right ``=` `getNode(``5``)  ` `    ``root.right.left ``=` `getNode(``6``)  ` `    ``root.right.right ``=` `getNode(``7``)  ` `         `  `    ``x ``=` `5` `    ``printPath(root, x) ` `     `  `# This code is contributed by PranchalK `

## C#

 `// C# implementation to print the path from root  ` `// to a given node in a binary tree  ` `using` `System; ` `using` `System.Collections; ` `using` `System.Collections.Generic; ` ` `  `class` `PrintPath  ` `{ ` `     `  `// A node of binary tree  ` `public` `class` `Node  ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node left, right;  ` `    ``public` `Node(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `        ``left = right = ``null``; ` `    ``} ` `} ` ` `  `    ``// Returns true if there is a path from root  ` `    ``// to the given node. It also populates  ` `    ``// 'arr' with the given path  ` `    ``public` `static` `Boolean hasPath(Node root, ` `                        ``List<``int``> arr, ``int` `x)  ` `    ``{  ` `        ``// if root is NULL  ` `        ``// there is no path  ` `        ``if` `(root == ``null``)  ` `            ``return` `false``;  ` `         `  `        ``// push the node's value in 'arr'  ` `        ``arr.Add(root.data);   ` `         `  `        ``// if it is the required node  ` `        ``// return true  ` `        ``if` `(root.data == x)   ` `            ``return` `true``;  ` `         `  `        ``// else check whether the required node lies  ` `        ``// in the left subtree or right subtree of  ` `        ``// the current node  ` `        ``if` `(hasPath(root.left, arr, x) ||  ` `            ``hasPath(root.right, arr, x))  ` `            ``return` `true``;  ` `         `  `        ``// required node does not lie either in the  ` `        ``// left or right subtree of the current node  ` `        ``// Thus, remove current node's value from  ` `        ``// 'arr'and then return false     ` `        ``arr.RemoveAt(arr.Count - 1);  ` `        ``return` `false``;             ` `    ``}  ` ` `  `    ``// function to print the path from root to the  ` `    ``// given node if the node lies in the binary tree  ` `    ``public` `static` `void` `printPath(Node root, ``int` `x)  ` `    ``{  ` `        ``// List to store the path  ` `        ``List<``int``> arr = ``new` `List<``int``>(); ` `     `  `        ``// if required node 'x' is present  ` `        ``// then print the path  ` `        ``if` `(hasPath(root, arr, x))  ` `        ``{  ` `            ``for` `(``int` `i = 0; i < arr.Count - 1; i++)   ` `                ``Console.Write(arr[i]+``"->"``); ` `            ``Console.Write(arr[arr.Count - 1]);  ` `        ``}  ` `         `  `        ``// 'x' is not present in the binary tree  ` `        ``else` `            ``Console.Write(``"No Path"``);  ` `    ``}  ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String []args)  ` `    ``{ ` `         `  `        ``Node root = ``new` `Node(1); ` `        ``root.left = ``new` `Node(2);  ` `        ``root.right = ``new` `Node(3);  ` `        ``root.left.left = ``new` `Node(4);  ` `        ``root.left.right = ``new` `Node(5);  ` `        ``root.right.left = ``new` `Node(6);  ` `        ``root.right.right = ``new` `Node(7);  ` `        ``int` `x=5; ` `         `  `        ``printPath(root, x); ` `    ``} ` `} ` ` `  `// This code is contributed by Arnab Kundu `

Output:

```1->2->5
```

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

Tree Tree