DFS O(n) time complexity. Detailed explanation with example.
Intuition\nThe intuition is the following: we should go through the tree visiting each node and calculate the coins value for the node based on the data provide
# Intuition\nThe intuition is the following: we should go through the tree visiting each node and calculate the coins value for the node based on the **data** provided to us by all the child nodes of the current node. So by the time we need to calculate the answer for the current node all the required data for its children should already be calculated. This gives us a hint of using DFS for solving this problem. This DFS skeleton logic will look smth like this:\n\n```\nDFS(int node)\n{\n    if (node is Leaf)\n    {\n        // Base case. If have a leaf node the answer is obvious\n        ...\n    }    \n\n    // Calculate the data for all children\n    foreach (var childNode in childNodes[node])\n    {\n        DFS(childNode);\n    }\n\n    // Calculate the answer based on the data we calculated for children\n    ...\n}\n```\n\nAnother question is what kind of **data** should be calculated.\nOf course we need to store the result coin value for the node in the **result array**, that we will return in the end:\n```\nlong[] result\n```\nBut unfortunately there is no way this specific data will help us finding the solution for other nodes, so there is smth else that needs to be stored.\nThe additional data we require is for sure the size of the current node subtree. We can easily calculate it knowing the size of each child\'s subtree:\n\n`int subtreeSize = 1 + child1Size + child2Size + ... + childKSize;`\n\nOther data that needs to be stored is 2 arrays: one for containing the 3 maximal posivitive elements in the subtree, another for containing 3 minimal negative (in fact 2 is enough, but for code simplicity we will store 3 as well as for the first case).\nWhy do we need this data? Think of the value we need to find for each node in case its\' subtree size is more than 2: ***the maximum product of cost values assigned to 3 distinct nodes in the subtree of the current node***.\nSo the main idea is that there are 2 values this ***maximum product*** could be equal to: its either the product of 3 maximal positive costs in the subtree or a product of 2 minimal negative costs and 1 highest positive one. And nothing else.\n\nWe can apply our logic to one of the examples given by leetcode:\n\n![screenshot-2023-11-10-012614.png](https://assets.leetcode.com/users/images/0672061c-78ad-428d-9dcf-fa9f598ac4cc_1704311135.5772643.png)\n\nAs you can see we first calculate the values for the leafs, then its parents and so on till the root. **Pay attention that the maximumPositives list contains elements in descending order. The minimumNegatives - vise versa.**\n\n# Approach\n- First we innialize basic variables and build the adjacency list to be able to go throw the tree during DFS:\n    ```\n    adjacencyList = new Dictionary<int, List<int>>();\n    n = cost.Length;\n    result = new long[n];\n    costs = cost;\n    for (int i = 0; i < edges.Length; i++)\n    {\n        int node1 = edges[i][0];\n        int node2 = edges[i][1];\n        AddNodePairToAdjacencyList(node1, node2);\n        AddNodePairToAdjacencyList(node2, node1);\n    }\n    ```\n- Then we launch DFS for the node 0. After the DFS is complete the result array should contain the valid answer, we return it.\n\nOur DFS method will have the following signature:\n\n`private (int size, List<int> positive, List<int> negative) DFSTreeSearch(int node, int previousNode)`,\n\nwhere node is the current node and the previousNode is passed in order to avoid infinite loop because our **tree is undirected**.\nThe method returns 3 data parameteres: size (size of the subtree for the passed node), positive (list of 3 maximum positive costs for the passed node subtree), negative (list of 3 minimum negative costs for the passed node subtree, **it could be 2 as well**, but **I left 3 for code simplicity**).\n\nThe base case of our DFS method is a leaf node: we can check if the current node is leaf with the following code:\n```\n    List<int> positive = new List<int>();\n    List<int> negative = new List<int>();\n    int subTreeSize = 1;\n\n    if (costs[node] < 0)\n    {\n        negative.Add(costs[node]);\n    }\n    else\n    {\n        positive.Add(costs[node]);\n    }\n\n    if (adjacencyList[node].Count == 1 && adjacencyList[node][0] == previousNode)\n    {\n        result[node] = 1;\n        return (subTreeSize, positive, negative);\n    }\n```\n\nAs you can see in the beginning of the method we define positive and negative lists and a subTreeSize variable, that we should return in the end when we finish the required calculations.\nIn the base case (leaf node) we set result[node] to 1, subTreeSize remains equal to 1 and its returned positive and negative lists contain either node itself or are empty.\n\nThen if the base case is not the case we go through all the child nodes and call the DFS method for each of them (meanwhile adjusting data for the negative and positive lists as well as calculating the current subtree size):\n```\nfor (int i = 0; i < adjacencyList[node].Count; i++)\n{\n    int nextNode = adjacencyList[node][i];\n    if (nextNode == previousNode)\n    {\n        continue;\n    }\n\n    var nodeData = DFSTreeSearch(nextNode, node);\n\n    subTreeSize += nodeData.size;\n\n    positive = MergeTwoLists(positive, nodeData.positive, PositiveComparer);\n    negative = MergeTwoLists(negative, nodeData.negative, NegativeComparer);\n}\n```\n\nPay attention to **MergeTwoLists** helper method. It accepts two **sorted lists** of maximum size 3 and returns **another sorted list** of maximum size 3 containing either maximum positive elements or minimal negative elements of the passed lists depending on the comparer method (the 3rd parameter of the method). **Because of the maximum size 3 we can assume that its time complexity is constant**:\n\n```\nprivate List<int> MergeTwoLists(List<int> first, List<int> second, Func<int, int, bool> comparer)\n{\n    List<int> newList = new List<int>();\n    int firstIndex = 0;\n    int secondIndex = 0;\n\n    while (firstIndex < first.Count && secondIndex < second.Count && newList.Count < 3)\n    {\n        if (comparer(first[firstIndex], second[secondIndex]))\n        {\n            newList.Add(first[firstIndex]);\n            firstIndex++;\n        }\n        else\n        {\n            newList.Add(second[secondIndex]);\n            secondIndex++;\n        }\n    }\n    if (newList.Count == 3)\n    {\n        return newList;\n    }\n    if (firstIndex >= first.Count)\n    {\n        while (secondIndex < second.Count && newList.Count < 3)\n        {\n            newList.Add(second[secondIndex]);\n            secondIndex++;\n        }\n        return newList;\n    }\n    while (firstIndex < first.Count && newList.Count < 3)\n    {\n        newList.Add(first[firstIndex]);\n        firstIndex++;\n    }\n    return newList;\n}\n```\n\nAfter all the required child data is collected we can calculate the final result data for the current node and return:\n\n```\nif (subTreeSize < 3)\n{\n    result[node] = 1;\n    return (subTreeSize, positive, negative);\n}\nlong onePosTwoNegSum = (positive.Count >= 1 && negative.Count >= 2) ? (long)positive[0] * negative[0] * negative[1] : 0;\nlong threePosSum = (positive.Count >= 3) ? (long)positive[0] * positive[1] * positive[2] : 0;\n\nresult[node] = Math.Max(onePosTwoNegSum, threePosSum);\nreturn (subTreeSize, positive, negative);\n```\n\n# Complexity\n- Time complexity:\n**The time complexity should be O(V + E), where V is the amount of tree nodes and E - edges. We know that V is equal to n and E to n - 1. So the final time complexity is equal to O(n).**\nWe spend O(E) time building our graph and initializing basic variables.\nThen in the DFS we go through every node (V nodes) and do some constant time operations (MergeTwoLists is constant as we discussed earlier) E times in sum for all nodes. That all sums up to O(V + E).\n\n- Space complexity:\n**O(n) because of recursion which maximum depth is n and adjacencyList which is also n sized.**\n\n# Code\n\nFinal code:\n```\npublic class Solution\n{\n    private Dictionary<int, List<int>> adjacencyList;\n    int n;\n    int[] costs;\n\n    long[] result;\n\n    public long[] PlacedCoins(int[][] edges, int[] cost)\n    {\n        adjacencyList = new Dictionary<int, List<int>>();\n        n = cost.Length;\n        result = new long[n];\n        costs = cost;\n\n        for (int i = 0; i < edges.Length; i++)\n        {\n            int node1 = edges[i][0];\n            int node2 = edges[i][1];\n\n            AddNodePairToAdjacencyList(node1, node2);\n            AddNodePairToAdjacencyList(node2, node1);\n        }\n\n        DFSTreeSearch(0, -1);\n\n        return result;\n    }\n\n    private (int size, List<int> positive, List<int> negative) DFSTreeSearch(int node, int previousNode)\n    {\n        List<int> positive = new List<int>();\n        List<int> negative = new List<int>();\n        int subTreeSize = 1;\n\n        if (costs[node] < 0)\n        {\n            negative.Add(costs[node]);\n        }\n        else\n        {\n            positive.Add(costs[node]);\n        }\n\n        if (adjacencyList[node].Count == 1 && adjacencyList[node][0] == previousNode)\n        {\n            result[node] = 1;\n            return (subTreeSize, positive, negative);\n        }\n\n        for (int i = 0; i < adjacencyList[node].Count; i++)\n        {\n            int nextNode = adjacencyList[node][i];\n\n            if (nextNode == previousNode)\n            {\n                continue;\n            }\n\n            var nodeData = DFSTreeSearch(nextNode, node);\n\n            subTreeSize += nodeData.size;\n\n            positive = MergeTwoLists(positive, nodeData.positive, PositiveComparer);\n            negative = MergeTwoLists(negative, nodeData.negative, NegativeComparer);\n        }\n\n        if (subTreeSize < 3)\n        {\n            result[node] = 1;\n            return (subTreeSize, positive, negative);\n        }\n\n        long onePosTwoNegSum = (positive.Count >= 1 && negative.Count >= 2) ? (long)positive[0] * negative[0] * negative[1] : 0;\n        long threePosSum = (positive.Count >= 3) ? (long)positive[0] * positive[1] * positive[2] : 0;\n\n        result[node] = Math.Max(onePosTwoNegSum, threePosSum);\n        return (subTreeSize, positive, negative);\n    }\n\n    private List<int> MergeTwoLists(List<int> first, List<int> second, Func<int, int, bool> comparer)\n    {\n        List<int> newList = new List<int>();\n\n        int firstIndex = 0;\n        int secondIndex = 0;\n\n        while (firstIndex < first.Count && secondIndex < second.Count && newList.Count < 3)\n        {\n            if (comparer(first[firstIndex], second[secondIndex]))\n            {\n                newList.Add(first[firstIndex]);\n                firstIndex++;\n            }\n            else\n            {\n                newList.Add(second[secondIndex]);\n                secondIndex++;\n            }\n        }\n\n        if (newList.Count == 3)\n        {\n            return newList;\n        }\n\n        if (firstIndex >= first.Count)\n        {\n            while (secondIndex < second.Count && newList.Count < 3)\n            {\n                newList.Add(second[secondIndex]);\n                secondIndex++;\n            }\n\n            return newList;\n        }\n\n        while (firstIndex < first.Count && newList.Count < 3)\n        {\n            newList.Add(first[firstIndex]);\n            firstIndex++;\n        }\n\n        return newList;\n    }\n\n    private bool PositiveComparer(int first, int second)\n    {\n        return first > second;\n    }\n\n    private bool NegativeComparer(int first, int second)\n    {\n        return first < second;\n    }\n\n    private void AddNodePairToAdjacencyList(int node1, int node2)\n    {\n        if (adjacencyList.ContainsKey(node1))\n        {\n            adjacencyList[node1].Add(node2);\n        }\n        else\n        {\n            adjacencyList.Add(node1, new List<int>() { node2 });\n        }\n    }\n}\n```
['Depth-First Search', 'C#']