Distance of each node of a Binary Tree from the root node using BFS

0 0 7 minutes read

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 i^th of the tree.
Traverse the tree using BFS. For every i^th 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 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<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 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<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 zambiatek!