What is time to live (TTL)?

Time to live (TTL) is a mechanism of associating a time-span with data packets in a network or computer system. It inhibits the indefinite circulation of those messages in the network by limiting their lifetime or lifespan.

Implementation

In this implementation, the network structure is represented by n-ary trees. The server can be at any node in the tree. We want to determine which nodes will successfully receive a message from the server, given a specific TTL value.

Let’s try to understand this better with an illustration:

Let’s see how we might implement this functionality:

Initialize the adjacency list.
Perform DFS on the root node and add every node’s parents and children to the adjacency list.
Mark the server node as the result and iterate TTL times over the adjacency list, starting from the server node.
During iteration, we will get all the parents and children nodes of the current node and mark them as the result.
When the loop ends, you’ll have the nodes that are TTL distance from the server as the result.

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public List<TreeNode> children;
    public TreeNode(int x) {
        val = x;
        children = new List<TreeNode>();
    }
};
class Solution {
    public static List<int> getDevices(TreeNode root, TreeNode server, int ttl) {  
        Dictionary<int, List<int>> neighbors = new Dictionary<int, List<int>>(); // Adjacency list
        dfs(null, root, neighbors);
        // BFS to find nodes
        List<int> bfs = new List<int>();
        bfs.Add(server.val);
        HashSet<int> lookup = new HashSet<int>(bfs);
        for (int i = 0; i < ttl; i++) {
            List<int> temp = new List<int>();
            foreach(int node in bfs)
                foreach(int nei in neighbors[node])
                    if (lookup.Contains(nei) == false)
                        temp.Add(nei);
            
            bfs = temp;
            lookup.UnionWith(bfs);
        }
        
        return bfs;
    }
    private static void dfs(TreeNode parent, TreeNode child, Dictionary<int, List<int>> neighbors) {
        // DFS to build adjacency list
        if (child == null){
                return;
        }
        if (parent != null) {
            if (!neighbors.ContainsKey(parent.val))
                neighbors[parent.val] = new List<int>();
            if (!neighbors.ContainsKey(child.val))
                neighbors[child.val] = new List<int>();
            neighbors[parent.val].Add(child.val);
            neighbors[child.val].Add(parent.val);
        }
        for (int i = 0; i < (child.children).Count; i++)
            dfs(child, child.children[i], neighbors);
    }
    public static void Main() {
        // Driver Code
        TreeNode root = new TreeNode(1);
        root.children.Add(new TreeNode(2));
        root.children.Add(new TreeNode(3));
        root.children.Add(new TreeNode(4));
        root.children[0].children.Add(new TreeNode(5));
        root.children[0].children[0].children.Add(new TreeNode(10));
        root.children[0].children.Add(new TreeNode(6));
        root.children[0].children[1].children.Add(new TreeNode(11));
        root.children[0].children[1].children.Add(new TreeNode(12));
        root.children[0].children[1].children.Add(new TreeNode(13));
        root.children[2].children.Add(new TreeNode(7));
        root.children[2].children.Add(new TreeNode(8));
        root.children[2].children.Add(new TreeNode(9));
        TreeNode server = root.children[0].children[1];
        int ttl = 2;
        Console.WriteLine("The TTL value will expire on node IDs: [{0}]", string.Join(", ", getDevices(root, server, ttl).ToArray()));
    }
}

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments