[Golang] DFS solution w/ merge sort & binary search (100%/100%)
Approach\nWith the goal in this problem of identifying the smallest missing "genetic" value in each subtree, our central focus is on how to structure the data. 
# Approach\nWith the goal in this problem of identifying the smallest missing "genetic" value in each subtree, our central focus is on how to structure the data. There are two key demands on that structure:\n1. Extracting the smallest missing value included within a _*given*_ subtree.\n2. Composing the data for a given subtree from that of (some of) the \n   _*other*_ subtrees.\n\n### Overall Processing Model\nSince this is _*trees*_ we\'re dealing with, the (obvious?) method to consider for that second aspect is composing the data for a given subtree by combining the value of the node at the root of that subtree with the data for the subtrees rooted at each of that node\'s children (if any). And that, of course, suggests some version of a depth-first traversal of the overall tree, composing the per-subtree information by working from the leaves up (noting that each leaf is a single-node subtree).\n\nThis gives us our core functional flow of a (familiar) recursive DFS function.\n\nIf we capture the values included in a given subtree as a simple slice of integers (`[]int`), then we can populate that slice by merging the (single) value of that subtree\'s root node with the slice of values associated with each of that node\'s children.  This, then, gives us the data type to be returned by our `dfs` function.\n\n### The Values in Each Subtree\nNow, back to that first consideration: extracting the minimum missing value from each subtree\'s slice of integers. This is much more tractable (and efficient) if each slice is sorted. Then, when merging the list from each of a node\'s children, we will be merging two sorted lists into one&mdash;a concept familiar from common merge-sort algorithms.\n\nHere, we constrain that operation\'s space consumption by merging the _*smaller*_ of the two slices into the _*larger*_ one, having first extended both the _*capacity*_ and _*size*_ of that larger slice by the size of the smaller one.\n\nNote that increasing the capacity of a slice is now explicitly provided by the `Grow` function in the `slices` package introduced in Go v1.21. We can then also increase the _*size*_ of the slice by slicing it accordingly. These steps are embodied in the following line from the full code (given below):\n```go\nmyCodes = slices.Grow(myCodes, nSmall)[:nNew]\n```\nThat extension may, of course, entail an internal allocation-and-copy operation, but does so automatically, efficiently, and only when needed.\n\n### Finding Each Subtree\'s Minimum Missing Value\nEven with the slices being ordered, finding the minimum missing value using a simple sequential loop gets expensive. So that operation is instead performed here via the `minMissing` function, which does a binary search on the given slice.\n\n### The Tree\nFinally (or should that be "initially"?), to obtain a workable tree structure with which we can do all of the above, we simply need to collate, for each node, all of the children for that node. So each node is represented by a slice of integers (`type Kids []int`), with those nodes held (and indexed) in a slice of `Kids`:\n```go\ntree := make([]Kids, n)\n```\nThis `tree` is populated very simply, from the given `parents` slice, in the opening lines of the function.\n\n<!--\n# Complexity\n- Time complexity: \n\n- Space complexity:\n-->\n### Performance\nLeetCode reports the following time & space consumption for this version:\n- Runtime: ~900 ms.\n- Memory: ~70 MB\n\nBoth of these are (currently) better than 100% of the solutions in Go from other users.\n\n# Code\nNote the included (but commented out) DEBUG statements. Activate some or all of these to see more details about how it works.  \n\n```go\ntype Kids []int\n\nfunc smallestMissingValueSubtree(parents, codes []int) []int {\n\t// Each of codes[i] is a distinct value in the range [1, 10^5].\n\tn := len(codes)\n\ttree := make([]Kids, n)\n\t// fmt.Printf("Root is code %d (index 0)\\n", codes[0]) // DEBUG\n\tfor i := 1; i < n; i++ {\n\t\ttree[parents[i]] = append(tree[parents[i]], i)\n\t}\n\tans := make([]int, n)\n\n\t// dfs returns a slice containing the ordered codes in subtree r.\n\tvar dfs func(r int) []int\n\tdfs = func(i int) []int {\n\t\tcode := codes[i]\n\t\t// fmt.Printf("dfs: got code %d (idx %d) w/ %d children\\n", code, i, len(tree[i])) // DEBUG\n\t\tif len(tree[i]) == 0 {\n\t\t\tans[i] = 3 - min(2, code) // That is: ans[i] = (code == 1 ? 2 : 1).\n\t\t\t// fmt.Printf("Exit dfs w/ 0 kids: ans[%d] = %d; subcodes: %v\\n", i, ans[i], []int{code})\n\t\t\treturn []int{code}\n\t\t}\n\t\tkid := tree[i][0]\n\t\tmyCodes := dfs(kid)\n\t\t// Merging this node\'s value into these codes of 1st kid is just a careful insertion (to keep it ordered).\n\t\tj, _ := slices.BinarySearch(myCodes, code)\n\t\tmyCodes = slices.Insert(myCodes, j, code)\n\t\tif code == ans[kid] {\n\t\t\tans[i] = minMissing(myCodes)\n\t\t} else {\n\t\t\tans[i] = ans[kid] // Because code must be larger than ans[kid].\n\t\t}\n\t\t// if len(tree[i]) > 1 {\n\t\t// fmt.Printf("  dfs checkpoint (code %d): finished kid 1 (of %d): ans[%d]: %d; kid\'s ans[%d]: %d; myCodes: %v\\n",\n\t\t//\tcode, len(tree[i]), i, ans[i], kid, ans[kid], myCodes)\n\t\t// }\n\t\tfor k := 1; k < len(tree[i]); k++ {\n\t\t\t// Process each child node & merge each resulting code list.\n\t\t\tkid := tree[i][k]\n\t\t\tsubCodes := dfs(kid)\n\t\t\tif len(subCodes) > len(myCodes) {\n\t\t\t\tmyCodes, subCodes = subCodes, myCodes\n\t\t\t}\n\t\t\t// Merge the two sorted slices into the larger one, after enlarging it accordingly.\n\t\t\t// Note: This reuses that larger slice, if it happened to already have capacity.\n\t\t\tnBig, nSmall := len(myCodes), len(subCodes)\n\t\t\tnNew := nBig + nSmall\n\t\t\tmyCodes = slices.Grow(myCodes, nSmall)[:nNew] // Grow changes only the capacity; then slice to extend the size.\n\t\t\tfor jBig, jSmall, jNew := nBig-1, nSmall-1, nNew-1; jSmall >= 0; {\n\t\t\t\t// Populate the expanded slice from the (initially empty) top down.\n\t\t\t\t// We\'re done when we\'ve pulled in the last (i.e., [0]) value from the smaller source slice.\n\t\t\t\tif jBig >= 0 && myCodes[jBig] > subCodes[jSmall] {\n\t\t\t\t\tmyCodes[jNew] = myCodes[jBig]\n\t\t\t\t\tjBig--\n\t\t\t\t} else {\n\t\t\t\t\tmyCodes[jNew] = subCodes[jSmall]\n\t\t\t\t\tjSmall--\n\t\t\t\t}\n\t\t\t\tjNew--\n\t\t\t}\n\t\t\tif ans[i] != ans[kid] {\n\t\t\t\tans[i] = minMissing(myCodes)\n\t\t\t}\n\t\t\t// fmt.Printf("  dfs checkpoint (code %d): finished kid %d (of %d): ans[%d]: %d; kid\'s ans[%d]: %d; myCodes: %v\\n",\n\t\t\t//\tcode, k+1, len(tree[i]), i, ans[i], kid, ans[kid], myCodes)\n\t\t}\n\t\t// fmt.Printf("Exit dfs of code %d (%d kids): ans[%d] = %d; myCodes: %v\\n", code, len(tree[i]), i, ans[i], myCodes)\n\t\treturn myCodes\n\t}\n\n\t_ = dfs(0)\n\treturn ans\n}\n\n// minMissing returns the smallest positive integer\n// absent from the given sorted slice.\nfunc minMissing(slc []int) int {\n\ttop := len(slc) - 1\n\tif slc[0] > 1 {\n\t\treturn 1\n\t}\n\tleft, right, mid := 0, top, 0\n\tfor left <= right {\n\t\tmid = left + (right-left+1)/2\n\t\tif slc[mid] > mid+1 {\n\t\t\tright = mid - 1\n\t\t} else if mid < top && slc[mid+1] == mid+2 {\n\t\t\tleft = mid + 1\n\t\t} else {\n\t\t\tbreak\n\t\t}\n\t}\n\treturn mid + 2\n}\n\n```\n
['Binary Search', 'Tree', 'Depth-First Search', 'Recursion', 'Merge Sort', 'Go']