# Find distance from root to given node in a binary tree

Given root of a binary tree and a key x in it, find distance of the given key from root. Dis­tance means num­ber of edges between two nodes.

Examples:

```Input : x = 45,
Root of below tree
5
/
10      15
/     /
20  25  30   35

45
Output : Distance = 3
There are three edges on path
from root to 45.

For more understanding of question,
in above tree distance of 35 is two
and distance of 10 is 1.
```

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

The idea is to traverse the tree from root. Check if x is present at root or in left subtree or in right subtree. We initialize distance as -1 and add 1 to distance for all three cases.

## C++

 `// C++ program to find distance of a given ` `// node from root. ` `#include ` `using` `namespace` `std; ` ` `  `// A Binary Tree Node ` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``Node *left, *right; ` `}; ` ` `  `// A utility function to create a new Binary ` `// Tree Node ` `Node *newNode(``int` `item) ` `{ ` `    ``Node *temp = ``new` `Node; ` `    ``temp->data = item; ` `    ``temp->left = temp->right = NULL; ` `    ``return` `temp; ` `} ` ` `  `// Returns -1 if x doesn't exist in tree. Else ` `// returns distance of x from root ` `int` `findDistance(Node *root, ``int` `x) ` `{ ` `    ``// Base case ` `    ``if` `(root == NULL) ` `      ``return` `-1; ` ` `  `    ``// Initialize distance ` `    ``int` `dist = -1; ` ` `  `    ``// Check if x is present at root or in left ` `    ``// subtree or right subtree. ` `    ``if` `((root->data == x) || ` `        ``(dist = findDistance(root->left, x)) >= 0 || ` `        ``(dist = findDistance(root->right, x)) >= 0) ` `        ``return` `dist + 1; ` ` `  `    ``return` `dist; ` `} ` ` `  `// Driver Program to test above functions ` `int` `main() ` `{ ` `    ``Node *root = newNode(5); ` `    ``root->left = newNode(10); ` `    ``root->right = newNode(15); ` `    ``root->left->left = newNode(20); ` `    ``root->left->right = newNode(25); ` `    ``root->left->right->right = newNode(45); ` `    ``root->right->left = newNode(30); ` `    ``root->right->right = newNode(35); ` ` `  `    ``cout << findDistance(root, 45); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find distance of a given  ` `// node from root.  ` `import` `java.util.*; ` `class` `GfG { ` ` `  `// A Binary Tree Node  ` `static` `class` `Node  ` `{  ` `    ``int` `data;  ` `    ``Node left, right;  ` `} ` ` `  `// A utility function to create a new Binary  ` `// Tree Node  ` `static` `Node newNode(``int` `item)  ` `{  ` `    ``Node temp = ``new` `Node();  ` `    ``temp.data = item;  ` `    ``temp.left = ``null``; ` `    ``temp.right = ``null``;  ` `    ``return` `temp;  ` `}  ` ` `  `// Returns -1 if x doesn't exist in tree. Else  ` `// returns distance of x from root  ` `static` `int` `findDistance(Node root, ``int` `x)  ` `{  ` `    ``// Base case  ` `    ``if` `(root == ``null``)  ` `    ``return` `-``1``;  ` ` `  `    ``// Initialize distance  ` `    ``int` `dist = -``1``;  ` ` `  `    ``// Check if x is present at root or in left  ` `    ``// subtree or right subtree.  ` `    ``if` `((root.data == x) ||  ` `        ``(dist = findDistance(root.left, x)) >= ``0` `||  ` `        ``(dist = findDistance(root.right, x)) >= ``0``)  ` `        ``return` `dist + ``1``;  ` ` `  `    ``return` `dist;  ` `}  ` ` `  `// Driver Program to test above functions  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``Node root = newNode(``5``);  ` `    ``root.left = newNode(``10``);  ` `    ``root.right = newNode(``15``);  ` `    ``root.left.left = newNode(``20``);  ` `    ``root.left.right = newNode(``25``);  ` `    ``root.left.right.right = newNode(``45``);  ` `    ``root.right.left = newNode(``30``);  ` `    ``root.right.right = newNode(``35``);  ` ` `  `    ``System.out.println(findDistance(root, ``45``));  ` `} ` `}  `

## Python3

 `# Python3 program to find distance of  ` `# a given node from root. ` ` `  `# A class to create a new Binary  ` `# Tree Node  ` `class` `newNode: ` `    ``def` `__init__(``self``, item): ` `        ``self``.data ``=` `item  ` `        ``self``.left ``=` `self``.right ``=` `None` ` `  `# Returns -1 if x doesn't exist in tree.  ` `# Else returns distance of x from root  ` `def` `findDistance(root, x): ` `     `  `    ``# Base case  ` `    ``if` `(root ``=``=` `None``):  ` `        ``return` `-``1` ` `  `    ``# Initialize distance  ` `    ``dist ``=` `-``1` ` `  `    ``# Check if x is present at root or ` `    ``# in left subtree or right subtree. ` `    ``if` `(root.data ``=``=` `x):  ` `        ``return` `dist ``+` `1` `    ``else``: ` `        ``dist ``=` `findDistance(root.left, x) ` `        ``if` `dist >``=` `0``: ` `            ``return` `dist ``+` `1` `        ``else``: ` `            ``dist ``=` `findDistance(root.right, x) ` `            ``if` `dist >``=` `0``: ` `                ``return` `dist ``+` `1` ` `  `    ``return` `dist ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``root ``=` `newNode(``5``)  ` `    ``root.left ``=` `newNode(``10``)  ` `    ``root.right ``=` `newNode(``15``)  ` `    ``root.left.left ``=` `newNode(``20``)  ` `    ``root.left.right ``=` `newNode(``25``)  ` `    ``root.left.right.right ``=` `newNode(``45``)  ` `    ``root.right.left ``=` `newNode(``30``)  ` `    ``root.right.right ``=` `newNode(``35``)  ` ` `  `    ``print``(findDistance(root, ``45``)) ` ` `  `# This code is contributed by PranchalK `

## C#

 `// C# program to find distance of a given  ` `// node from root.  ` `using` `System; ` ` `  `class` `GfG  ` `{ ` ` `  `    ``// A Binary Tree Node  ` `    ``class` `Node  ` `    ``{  ` `        ``public` `int` `data;  ` `        ``public` `Node left, right;  ` `    ``} ` ` `  `    ``// A utility function to create   ` `    ``// a new Binary Tree Node  ` `    ``static` `Node newNode(``int` `item)  ` `    ``{  ` `        ``Node temp = ``new` `Node();  ` `        ``temp.data = item;  ` `        ``temp.left = ``null``; ` `        ``temp.right = ``null``;  ` `        ``return` `temp;  ` `    ``}  ` ` `  `    ``// Returns -1 if x doesn't exist in tree. Else  ` `    ``// returns distance of x from root  ` `    ``static` `int` `findDistance(Node root, ``int` `x)  ` `    ``{  ` `        ``// Base case  ` `        ``if` `(root == ``null``)  ` `        ``return` `-1;  ` ` `  `        ``// Initialize distance  ` `        ``int` `dist = -1;  ` ` `  `        ``// Check if x is present at root or in left  ` `        ``// subtree or right subtree.  ` `        ``if` `((root.data == x) ||  ` `            ``(dist = findDistance(root.left, x)) >= 0 ||  ` `            ``(dist = findDistance(root.right, x)) >= 0)  ` `            ``return` `dist + 1;  ` ` `  `        ``return` `dist;  ` `    ``}  ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `Main(String[] args)  ` `    ``{  ` `        ``Node root = newNode(5);  ` `        ``root.left = newNode(10);  ` `        ``root.right = newNode(15);  ` `        ``root.left.left = newNode(20);  ` `        ``root.left.right = newNode(25);  ` `        ``root.left.right.right = newNode(45);  ` `        ``root.right.left = newNode(30);  ` `        ``root.right.right = newNode(35);  ` ` `  `        ``Console.WriteLine(findDistance(root, 45));  ` `    ``} ` `} ` ` `  `// This code is contributed by 29AjayKumar `

Output:

```3
```

Tree Tree