Given a Binary tree consisting of N nodes with values in the range [1, N], the task is to find the distance from the root node to every node of the tree.
Examples:
Input:
1 / \ 2 3 / \ \ 4 5 6Output: 0 1 1 2 2 2
Explanation:
The distance from the root to node 1 is 0.
The distance from the root to node 2 is 1.
The distance from the root to node 3 is 1.
The distance from the root to node 4 is 2.
The distance from the root to node 5 is 2.
The distance from the root to node 6 is 2.
Input:
5 / \ 4 6 / \ 3 7 / \ 1 2Output: 3 3 2 1 0 1 2
Approach: The problem can be solved using BFS technique. The idea is to use the fact that the distance from the root to a node is equal to the level of that node in the binary tree. Follow the steps below to solve the problem:
- Initialize a queue, say Q, to store the nodes at each level of the tree.
- Initialize an array, say dist[], where dist[i] stores the distance from the root node to ith of the tree.
- Traverse the tree using BFS. For every ith node encountered, update dist[i] to the level of that node in the binary tree.
- Finally, print the dist[] array.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;struct Node { // Stores data value // of the node int data; // Stores left subtree // of a node Node* left; // Stores right subtree // of a node Node* right; Node(int x) { data = x; left = right = NULL; }};void findDistance(Node* root, int N){ // Store nodes at each level // of the binary tree queue<Node*> Q; // Insert root into Q Q.push(root); // Stores level of a node int level = 0; // dist[i]: Stores the distance // from root node to node i int dist[N + 1]; // Traverse tree using BFS while (!Q.empty()) { // Stores count of nodes // at current level int M = Q.size(); // Traverse the nodes at // current level for (int i = 0; i < M; i++) { // Stores front element // of the queue root = Q.front(); // Pop front element // of the queue Q.pop(); // Stores the distance from // root node to current node dist[root->data] = level; if (root->left) { // Push left subtree Q.push(root->left); } if (root->right) { // Push right subtree Q.push(root->right); } } // Update level level += 1; } for (int i = 1; i <= N; i++) { cout << dist[i] << " "; }}// Driver Codeint main(){ int N = 7; Node* root = new Node(5); root->left = new Node(4); root->right = new Node(6); root->left->left = new Node(3); root->left->right = new Node(7); root->left->left->left = new Node(1); root->left->left->right = new Node(2); findDistance(root, N);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{static class Node { // Stores data value // of the node int data; // Stores left subtree // of a node Node left; // Stores right subtree // of a node Node right; Node(int x) { data = x; left = right = null; }};static void findDistance(Node root, int N){ // Store nodes at each level // of the binary tree Queue<Node> Q = new LinkedList<>(); // Insert root into Q Q.add(root); // Stores level of a node int level = 0; // dist[i]: Stores the distance // from root node to node i int []dist = new int[N + 1]; // Traverse tree using BFS while (!Q.isEmpty()) { // Stores count of nodes // at current level int M = Q.size(); // Traverse the nodes at // current level for (int i = 0; i < M; i++) { // Stores front element // of the queue root = Q.peek(); // Pop front element // of the queue Q.remove(); // Stores the distance from // root node to current node dist[root.data] = level; if (root.left != null) { // Push left subtree Q.add(root.left); } if (root.right != null) { // Push right subtree Q.add(root.right); } } // Update level level += 1; } for (int i = 1; i <= N; i++) { System.out.print(dist[i] + " "); }}// Driver Codepublic static void main(String[] args){ int N = 7; Node root = new Node(5); root.left = new Node(4); root.right = new Node(6); root.left.left = new Node(3); root.left.right = new Node(7); root.left.left.left = new Node(1); root.left.left.right = new Node(2); findDistance(root, N);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program to implement# the above approachclass Node: def __init__(self, data): # Stores data value # of the node self.data = data # Stores left subtree # of a node self.left = None # Stores right subtree # of a node self.right = Nonedef findDistance(root, N): # Store nodes at each level # of the binary tree Q = [] # Insert root into Q Q.append(root) # Stores level of a node level = 0 # dist[i]: Stores the distance # from root node to node i dist = [0 for i in range(N + 1)] # Traverse tree using BFS while Q: # Stores count of nodes # at current level M = len(Q) # Traverse the nodes at # current level for i in range(0, M): # Stores front element # of the queue root = Q[0] # Pop front element # of the queue Q.pop(0) # Stores the distance from # root node to current node dist[root.data] = level if root.left: # Push left subtree Q.append(root.left) if root.right: # Push right subtree Q.append(root.right) # Update level level += 1 for i in range(1, N + 1): print(dist[i], end = " ")# Driver codeif __name__ == '__main__': N = 7 root = Node(5) root.left = Node(4) root.right = Node(6) root.left.left = Node(3) root.left.right = Node(7) root.left.left.left = Node(1) root.left.left.right = Node(2) findDistance(root, N)# This code is contributed by MuskanKalra1 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ class Node { // Stores data value // of the node public int data; // Stores left subtree // of a node public Node left; // Stores right subtree // of a node public Node right; public Node(int x) { data = x; left = right = null; } }; static void findDistance(Node root, int N) { // Store nodes at each level // of the binary tree Queue<Node> Q = new Queue<Node>(); // Insert root into Q Q.Enqueue(root); // Stores level of a node int level = 0; // dist[i]: Stores the distance // from root node to node i int []dist = new int[N + 1]; // Traverse tree using BFS while (Q.Count != 0) { // Stores count of nodes // at current level int M = Q.Count; // Traverse the nodes at // current level for (int i = 0; i < M; i++) { // Stores front element // of the queue root = Q.Peek(); // Pop front element // of the queue Q.Dequeue(); // Stores the distance from // root node to current node dist[root.data] = level; if (root.left != null) { // Push left subtree Q.Enqueue(root.left); } if (root.right != null) { // Push right subtree Q.Enqueue(root.right); } } // Update level level += 1; } for (int i = 1; i <= N; i++) { Console.Write(dist[i] + " "); } } // Driver Code public static void Main(String[] args) { int N = 7; Node root = new Node(5); root.left = new Node(4); root.right = new Node(6); root.left.left = new Node(3); root.left.right = new Node(7); root.left.left.left = new Node(1); root.left.left.right = new Node(2); findDistance(root, N); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to implement the above approach // Structure of a tree node class Node { constructor(x) { this.left = null; this.right = null; this.data = x; } } function findDistance(root, N) { // Store nodes at each level // of the binary tree let Q = []; // Insert root into Q Q.push(root); // Stores level of a node let level = 0; // dist[i]: Stores the distance // from root node to node i let dist = new Array(N + 1); // Traverse tree using BFS while (Q.length > 0) { // Stores count of nodes // at current level let M = Q.length; // Traverse the nodes at // current level for (let i = 0; i < M; i++) { // Stores front element // of the queue root = Q[0]; // Pop front element // of the queue Q.shift(); // Stores the distance from // root node to current node dist[root.data] = level; if (root.left != null) { // Push left subtree Q.push(root.left); } if (root.right != null) { // Push right subtree Q.push(root.right); } } // Update level level += 1; } for (let i = 1; i <= N; i++) { document.write(dist[i] + " "); } } let N = 7; let root = new Node(5); root.left = new Node(4); root.right = new Node(6); root.left.left = new Node(3); root.left.right = new Node(7); root.left.left.left = new Node(1); root.left.left.right = new Node(2); findDistance(root, N);</script> |
Output:
3 3 2 1 0 1 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
