Find distance from root to given node in a binary tree
Given the root of a binary tree and a key x in it, find the distance of the given key from the root. Distance means the number 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.
Approach: The idea is to traverse the tree from the root. Check if x is present at the root or in the left subtree or in the right subtree. We initialize distance as -1 and add 1 to distance for all three cases.
Implementation:
C++
// C++ program to find distance of a given // node from root. #include <bits/stdc++.h> 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 |
Javascript
<script> // Javascript program to find distance // of a given node from root. // A Binary Tree Node class Node { // A utility function to create a // new Binary Tree Node constructor(data) { this .data = data; this .left = this .right = null ; } } // Returns -1 if x doesn't exist in tree. Else // returns distance of x from root function findDistance(root, x) { // Base case if (root == null ) return -1; // Initialize distance let 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 let root = new Node(5); root.left = new Node(10); root.right = new Node(15); root.left.left = new Node(20); root.left.right = new Node(25); root.left.right.right = new Node(45); root.right.left = new Node(30); root.right.right = new Node(35); document.write(findDistance(root, 45)); // This code is contributed by rag2127 </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 2: Iterative Approach
The above recursive approach can also be converted to an iterative approach by using a queue. Here is the iterative approach:
- Start from the root node of the binary tree.
- Create a queue and add the root node to the queue.
- Create a map to store the parent of each node. Initialize the map with the root node’s parent as NULL.
- Create a variable to keep track of the distance from the root node.
- While the queue is not empty, dequeue a node and check if it is the target node.
- If the node is the target node, return the distance from the root node.
- If the node is not the target node, enqueue its left and right children (if they exist) and update their parent in the map.
- Increment the distance from the root node.
- Repeat steps 5-8 until the queue is empty or the target node is found.
C++
// C++ program to find distance of a given // node from root. #include <bits/stdc++.h> 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) { if (root == NULL) { return -1; } queue<Node*> q; q.push(root); int dist = 0; while (!q.empty()) { int size = q.size(); for ( int i = 0; i < size; i++) { Node* curr = q.front(); q.pop(); if (curr->data == x) { return dist; } if (curr->left) { q.push(curr->left); } if (curr->right) { q.push(curr->right); } } dist++; } return -1; } // 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 code for the above approach import java.util.LinkedList; import java.util.Queue; public class Main { static class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } // Returns -1 if x doesn't exist in the tree. Else returns the distance of x from the root static int findDistance(Node root, int x) { if (root == null ) { return - 1 ; } Queue<Node> queue = new LinkedList<>(); queue.add(root); int dist = 0 ; while (!queue.isEmpty()) { int size = queue.size(); for ( int i = 0 ; i < size; i++) { Node curr = queue.poll(); if (curr.data == x) { return dist; } if (curr.left != null ) { queue.add(curr.left); } if (curr.right != null ) { queue.add(curr.right); } } dist++; } return - 1 ; } // Driver Program to test above functions public static void main(String[] args) { Node root = new Node( 5 ); root.left = new Node( 10 ); root.right = new Node( 15 ); root.left.left = new Node( 20 ); root.left.right = new Node( 25 ); root.left.right.right = new Node( 45 ); root.right.left = new Node( 30 ); root.right.right = new Node( 35 ); System.out.println(findDistance(root, 45 )); } } |
Python3
# Python Program for the above approach from queue import Queue # A Binary Tree Node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Returns -1 if x doesn't exist in tree. Else # returns distance of x from root def findDistance(root, x): if root is None : return - 1 q = Queue() q.put(root) dist = 0 # till queue is not empty while not q.empty(): size = q.qsize() for i in range (size): curr = q.get() if curr.data = = x: return dist if curr.left: q.put(curr.left) if curr.right: q.put(curr.right) dist + = 1 return - 1 # Driver Program to test above functions if __name__ = = '__main__' : root = Node( 5 ) root.left = Node( 10 ) root.right = Node( 15 ) root.left.left = Node( 20 ) root.left.right = Node( 25 ) root.left.right.right = Node( 45 ) root.right.left = Node( 30 ) root.right.right = Node( 35 ) print (findDistance(root, 45 )) # This Code is contributed by Kirti Agarwal |
C#
using System; using System.Collections.Generic; public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } public class GFG { // Returns -1 if x doesn't exist in tree. Else // returns distance of x from root public static int FindDistance(Node root, int x) { if (root == null ) { return -1; } Queue<Node> q = new Queue<Node>(); q.Enqueue(root); int dist = 0; while (q.Count > 0) { int size = q.Count; for ( int i = 0; i < size; i++) { Node curr = q.Dequeue(); if (curr.data == x) { return dist; } if (curr.left != null ) { q.Enqueue(curr.left); } if (curr.right != null ) { q.Enqueue(curr.right); } } dist++; } return -1; } // Driver Program to // test above functions public static void Main() { Node root = new Node(5); root.left = new Node(10); root.right = new Node(15); root.left.left = new Node(20); root.left.right = new Node(25); root.left.right.right = new Node(45); root.right.left = new Node(30); root.right.right = new Node(35); Console.WriteLine(FindDistance(root, 45)); } } |
Javascript
// A Binary Tree Node class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Returns -1 if x doesn't exist in tree. Else // returns distance of x from root function findDistance(root, x) { if (root === null ) { return -1; } let queue = []; queue.push(root); let dist = 0; while (queue.length > 0) { let size = queue.length; for (let i = 0; i < size; i++) { let curr = queue.shift(); if (curr.data === x) { return dist; } if (curr.left) { queue.push(curr.left); } if (curr.right) { queue.push(curr.right); } } dist++; } return -1; } // Driver Program to test above functions let root = new Node(5); root.left = new Node(10); root.right = new Node(15); root.left.left = new Node(20); root.left.right = new Node(25); root.left.right.right = new Node(45); root.right.left = new Node(30); root.right.right = new Node(35); console.log(findDistance(root, 45)); // THIS CODE IS CONTRIBUTED BY Kirti Agarwal |
Output
3
Time Complexity: O(n) where n is the number of nodes in the tree.
Space Complexity: O(w) where w is the maximum width of the tree.
Contact Us