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
The text passage describes a problem related to finding the distance from the root node to every node in a binary tree using the Breadth-First Search (BFS) technique. It includes an example and a detailed approach, followed by code implementations in C++, Java, Python, and C#.

### Analysis:
no_question

the passage does not contain a specific mathematical question or a word problem that requires a solution. instead, it provides a problem statement, an approach, and code implementations. the examples given are used to illustrate the problem and the expected output, but they are not framed as questions.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
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
user
The text passage describes a problem related to finding the distance from the root node to every node in a binary tree using the Breadth-First Search (BFS) technique. It includes an example and a detailed approach, followed by code implementations in C++, Java, Python, and C#.

### Analysis:
TYPE: NO_QUESTION

The passage does not contain a specific mathematical question or a word problem that requires a solution. Instead, it provides a problem statement, an approach, and code implementations. The examples given are used to illustrate the problem and the expected output, but they are not framed as questions.