Minimizing Signal Propagation Time in a Binary Tree using BFS
Start from the given node “start” and use a Breadth-First Search (BFS) approach. Propagate signal to neighboring nodes during the BFS process and keep track of time until all nodes have been visited. To handle the issue of determining a node’s parent, create a data structure that maintains parent-node relationships, this will allowing to track each node’s parent.
Step-by-step approach:
- Store parent-child relationships for each node using a parent[] array.
- Find the given start node in the tree.
- Initilise a queue for BFS and a visited[] array to track nodes which received signal.
- While the queue is not empty:
- For each level of nodes in the queue:
- If the current node’s parent exists and didn’t receive signal, mark it as visited and add it to the queue.
- If the left child of the current node exists and didn’t receive signal, mark it as visited and add it to the queue.
- If the right child of the current node exists and didn’t receive signal, mark it as visited and add it to the queue.
- Increment the time (or, result) by 1.
- For each level of nodes in the queue:
- Finally, return the time (or, result).
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // A Tree node struct Node { int val; struct Node *left, *right; }; // Utility function to create a new node Node* newNode( int val) { Node* temp = new Node; temp->val = val; temp->left = temp->right = NULL; return (temp); } // "node" will store the actual Tree node // of special node "start". Node* node = NULL; // Function for generating // parent-root relationship void findParent(Node* root, Node* p, vector<Node*>& parent, int start) { if (root == NULL) return ; // Store parent of current node parent[root->val] = p; if (root->val == start) { node = root; } findParent(root->left, root, parent, start); findParent(root->right, root, parent, start); } // Function to return the minimum amount // of time require to Propagate signal all the // nodes of binary tree int amountOfTime(Node* root, int start) { vector<Node*> parent(100005, NULL); findParent(root, NULL, parent, start); vector< bool > visited(100005, false ); queue<Node*> q; // Push special tree node into the // queue and make it visited. q.push(node); visited[start] = true ; // This store the minimum time require // to Propagate signal all the tree node. int result = -1; while (q.size() > 0) { int n = q.size(); for ( int i = 0; i < n; i++) { auto curr = q.front(); int currNode = curr->val; q.pop(); // Check if parent of currNode // exist and not visited yet // then push this parent of // current node into queue. if (parent[currNode] != NULL && visited[parent[currNode]->val] == false ) { visited[parent[currNode]->val] = true ; q.push(parent[currNode]); } // Check if current node left // child exist and not // visited yet. if (curr->left && visited[curr->left->val] == false ) { visited[curr->left->val] = true ; q.push(curr->left); } // Check if current node right // child exist and not // visited yet. if (curr->right && visited[curr->right->val] == false ) { visited[curr->right->val] = true ; q.push(curr->right); } } // Increment the time result++; } // Return the result. return result; } // Driver Code int main() { /* 11 / \ 12 13 / \ 14 15 / \ / \ 21 22 23 24 Let us create Binary Tree as shown above */ Node* root = newNode(11); root->left = newNode(12); root->right = newNode(13); root->right->left = newNode(14); root->right->right = newNode(15); root->right->left->left = newNode(21); root->right->left->right = newNode(22); root->right->right->left = newNode(23); root->right->right->right = newNode(24); int start = 14; // Function call int result = amountOfTime(root, start); cout << result << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; class Node { int val; Node left, right; public Node( int val) { this .val = val; this .left = null ; this .right = null ; } } public class BinaryTreePropagationTime { static Node node = null ; public static Node newNode( int val) { // Create a new Node with the given value Node temp = new Node(val); return temp; } // Function for generating parent-root relationship public static void findParent(Node root, Node p, ArrayList<Node> parent, int start) { if (root == null ) return ; // Store the parent of the current node parent.set(root.val, p); if (root.val == start) { node = root; // Store the special node with the // given value } findParent(root.left, root, parent, start); findParent(root.right, root, parent, start); } // Function to return the minimum amount of time // required to propagate a signal in the binary tree public static int amountOfTime(Node root, int start) { ArrayList<Node> parent = new ArrayList<>(); for ( int i = 0 ; i < 100005 ; i++) { parent.add( null ); } findParent(root, null , parent, start); boolean [] visited = new boolean [ 100005 ]; Queue<Node> q = new LinkedList<>(); // Push the special tree node into the queue and // mark it as visited. q.add(node); visited[start] = true ; // This variable stores the minimum time required to // propagate the signal to all the tree nodes. int result = - 1 ; while (!q.isEmpty()) { int n = q.size(); for ( int i = 0 ; i < n; i++) { Node curr = q.poll(); int currNode = curr.val; // Check if the parent of currNode exists // and has not been visited yet. If so, push // the parent node into the queue. if (parent.get(currNode) != null && !visited[parent.get(currNode).val]) { visited[parent.get(currNode).val] = true ; q.add(parent.get(currNode)); } // Check if the left child of the current // node exists and has not been visited yet. if (curr.left != null && !visited[curr.left.val]) { visited[curr.left.val] = true ; q.add(curr.left); } // Check if the right child of the current // node exists and has not been visited yet. if (curr.right != null && !visited[curr.right.val]) { visited[curr.right.val] = true ; q.add(curr.right); } } // Increment the time result++; } // Return the result return result; } public static void main(String[] args) { // Create the binary tree as shown in the example Node root = newNode( 11 ); root.left = newNode( 12 ); root.right = newNode( 13 ); root.right.left = newNode( 14 ); root.right.right = newNode( 15 ); root.right.left.left = newNode( 21 ); root.right.left.right = newNode( 22 ); root.right.right.left = newNode( 23 ); root.right.right.right = newNode( 24 ); int start = 14 ; // Function call int result = amountOfTime(root, start); System.out.println(result); } } |
Python
from collections import deque class Node: def __init__( self , val): self .val = val self .left = None self .right = None def GFG(val): # Create a new Node with given value temp = Node(val) return temp def findParent(root, p, parent, start): if root is None : return # Store the parent of current node parent[root.val] = p if root.val = = start: global node node = root # Store the special node with given value findParent(root.left, root, parent, start) findParent(root.right, root, parent, start) def amountOfTime(root, start): parent = [ None ] * 100005 findParent(root, None , parent, start) visited = [ False ] * 100005 q = deque() # Push the special tree node into queue and mark it as visited. q.append(node) visited[start] = True # This variable stores the minimum time required to # propagate the signal to all the tree nodes. result = - 1 while q: n = len (q) for i in range (n): curr = q.popleft() currNode = curr.val # Check if the parent of the currNode exists and has not been visited yet. if parent[currNode] is not None and not visited[parent[currNode].val]: visited[parent[currNode].val] = True q.append(parent[currNode]) # Check if the left child of current node exists and has not been visited yet. if curr.left is not None and not visited[curr.left.val]: visited[curr.left.val] = True q.append(curr.left) # Check if the right child of the current node exists and # has not been visited yet. if curr.right is not None and not visited[curr.right.val]: visited[curr.right.val] = True q.append(curr.right) # Increment the time result + = 1 # Return the result return result if __name__ = = "__main__" : # Create the binary tree as shown the example root = GFG( 11 ) root.left = GFG( 12 ) root.right = GFG( 13 ) root.right.left = GFG( 14 ) root.right.right = GFG( 15 ) root.right.left.left = GFG( 21 ) root.right.left.right = GFG( 22 ) root.right.right.left = GFG( 23 ) root.right.right.right = GFG( 24 ) start = 14 # Function call result = amountOfTime(root, start) print (result) |
C#
// C# code for the above approach using System; using System.Collections.Generic; // A Tree node public class Node { public int val; public Node left, right; } public class GFG { // Utility function to create a new node public static Node newNode( int val) { Node temp = new Node(); temp.val = val; temp.left = temp.right = null ; return temp; } // "node" will store the actual Tree node // of special node "start". public static Node node = null ; // Function for generating parent-root relationship public static void findParent(Node root, Node p, List<Node> parent, int start) { if (root == null ) return ; // Store parent of current node parent[root.val] = p; if (root.val == start) { node = root; } findParent(root.left, root, parent, start); findParent(root.right, root, parent, start); } // Function to return the minimum amount // of time require to Propagate signal all the // nodes of binary tree public static int amountOfTime(Node root, int start) { List<Node> parent = new List<Node>(100005); for ( int i = 0; i < 100005; i++) { parent.Add( null ); } findParent(root, null , parent, start); bool [] visited = new bool [100005]; Queue<Node> q = new Queue<Node>(); // Push special tree node into the // queue and make it visited. q.Enqueue(node); visited[start] = true ; // This store the minimum time require // to Propagate signal all the tree node. int result = -1; while (q.Count > 0) { int n = q.Count; for ( int i = 0; i < n; i++) { var curr = q.Dequeue(); int currNode = curr.val; // Check if parent of currNode // exist and not visited yet // then push this parent of // current node into queue. if (parent[currNode] != null && visited[parent[currNode].val] == false ) { visited[parent[currNode].val] = true ; q.Enqueue(parent[currNode]); } // Check if current node left // child exist and not // visited yet. if (curr.left != null && visited[curr.left.val] == false ) { visited[curr.left.val] = true ; q.Enqueue(curr.left); } // Check if current node right // child exist and not // visited yet. if (curr.right != null && visited[curr.right.val] == false ) { visited[curr.right.val] = true ; q.Enqueue(curr.right); } } // Increment the time result++; } // Return the result. return result; } // Driver Code public static void Main( string [] args) { /* 11 / \ 12 13 / \ 14 15 / \ / \ 21 22 23 24 Let us create Binary Tree as shown above */ Node root = newNode(11); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); int start = 14; // Function call int result = amountOfTime(root, start); Console.WriteLine(result); } } |
Javascript
// Javascript code for the above approach // A Tree node class Node { constructor(val) { this .val = val; this .left = null ; this .right = null ; } } // Utility function to create a new node function newNode(val) { const temp = new Node(val); temp.left = null ; temp.right = null ; return temp; } // "node" will store the actual Tree node // of the special node "start". let node = null ; // Function for generating // parent-root relationship function findParent(root, p, parent, start) { if (root === null ) { return ; } // Store parent of the current node parent[root.val] = p; if (root.val === start) { node = root; } findParent(root.left, root, parent, start); findParent(root.right, root, parent, start); } // Function to return the minimum amount // of time required to propagate signal to all the nodes of a binary tree function amountOfTime(root, start) { const parent = Array(100005).fill( null ); findParent(root, null , parent, start); const visited = Array(100005).fill( false ); const q = []; // Push the special tree node into the // queue and mark it as visited. q.push(node); visited[start] = true ; // This stores the minimum time required // to propagate the signal to all the tree nodes. let result = -1; while (q.length > 0) { const n = q.length; for (let i = 0; i < n; i++) { const curr = q.shift(); const currNode = curr.val; // Check if the parent of currNode // exists and is not visited yet, // then push this parent of // the current node into the queue. if (parent[currNode] !== null && !visited[parent[currNode].val]) { visited[parent[currNode].val] = true ; q.push(parent[currNode]); } // Check if the left child of the current node exists and is not visited yet. if (curr.left && !visited[curr.left.val]) { visited[curr.left.val] = true ; q.push(curr.left); } // Check if the right child of the current node exists and is not visited yet. if (curr.right && !visited[curr.right.val]) { visited[curr.right.val] = true ; q.push(curr.right); } } // Increment the time result++; } // Return the result. return result; } // Driver Code // Create the binary tree const root = newNode(11); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); const start = 14; // Function call const result = amountOfTime(root, start); console.log(result); // This code is contributed by ragul21 |
3
Time Complexity: O(N), where N is the number of nodes in the binary tree.
Auxiliary Space: O(N)
Minimizing Signal Propagation Time in a Binary Tree
Given a binary tree and a source node “start” which transmits a network signal. The signal propagates to neighboring nodes every second, the task is to determine the minimum amount of time required for the entire tree to receive the signal.
Examples:
Input:
11
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Start = 14
Output: 3Input:
4
/ \
3 1
\
2
Start = 1
Output: 2