text: Related Articles
  
  # Distance of each node of a Binary Tree from the root node using BFS
  
  • Last Updated : 21 Jun, 2021
  
  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   6```
  
  Output: 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    2```
  
  Output: 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 ``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 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 Code``int` `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 approach``import` `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 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 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`
  
  ## Python3
  
   `# Python3 program to implement``# the above approach``class` `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 ``=` `None` `def` `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 code``if` `__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 approach``using` `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 Q = ``new` `Queue();` `    ``// 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
  
   ``
  Output:
  `3 3 2 1 0 1 2`
  
  Time Complexity: O(N)
  Auxiliary Space: O(N)
  
  Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.
  
  In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.
  
  My Personal Notes arrow_drop_up
explanation: The provided text extract is a technical article that explains how to find the distance from the root node to every node in a binary tree using the Breadth-First Search (BFS) algorithm. The article includes examples, a detailed approach, and code implementations in C++, Java, Python, and C#.
  
  The text does not contain a specific question or a question-and-answer format. It is primarily an explanation and implementation of an algorithm.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: Related Articles
  
  # Distance of each node of a Binary Tree from the root node using BFS
  
  • Last Updated : 21 Jun, 2021
  
  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   6```
  
  Output: 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    2```
  
  Output: 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 ``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 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 Code``int` `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 approach``import` `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 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 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`
  
  ## Python3
  
   `# Python3 program to implement``# the above approach``class` `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 ``=` `None` `def` `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 code``if` `__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 approach``using` `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 Q = ``new` `Queue();` `    ``// 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
  
   ``
  Output:
  `3 3 2 1 0 1 2`
  
  Time Complexity: O(N)
  Auxiliary Space: O(N)
  
  Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.
  
  In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.
  
  My Personal Notes arrow_drop_up
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text extract is a technical article that explains how to find the distance from the root node to every node in a binary tree using the Breadth-First Search (BFS) algorithm. The article includes examples, a detailed approach, and code implementations in C++, Java, Python, and C#.
  
  The text does not contain a specific question or a question-and-answer format. It is primarily an explanation and implementation of an algorithm.
  
  Label: no-question