Ruby Solution O(n)
\n\n# TRICK WAS TO FIND NODE OF 1 \n# MARK(IN MISSED_ARRAY) EVERY CHILDREN VALUE OF 1 VALUE NODE  (DFS)\n# FIND FIRST AVAILABLE EMPTY SPOT IN MISSED_ARRAY (DYNA
```\n\n# TRICK WAS TO FIND NODE OF 1 \n# MARK(IN MISSED_ARRAY) EVERY CHILDREN VALUE OF 1 VALUE NODE  (DFS)\n# FIND FIRST AVAILABLE EMPTY SPOT IN MISSED_ARRAY (DYNAMIC VALUES ARRAY)\n# SET RESULT ARRAY AT NODE INDEX = MISSED_INDEX\n# MAKE NEW NODE TO BE THE PARENT OF 1\n# REAPEAT THIS PROCESS UNTILL YOU REACH ROOT\n\n\ndef dfs(idx, missed_map, children_list, nums)\n    return if missed_map[nums[idx]] == true\n    children_list[idx].each do |child_idx|\n        dfs(child_idx, missed_map, children_list, nums)\n    end\n    missed_map[nums[idx]] = true\nend\n\ndef create_children_adjacency_list(parents, nums)\n    children_list = Array.new(nums.length) {Array.new} \n    for i in 1..parents.length-1\n        children_list[parents[i]] << i\n    end\n    children_list\nend\n\ndef find_first_missed_number(nums, missed_map, children_list, result, parents)\n    idx = nums.index(1)\n    missed = 1\n    while idx >= 0\n        dfs(idx, missed_map, children_list, nums)\n        while(missed_map[missed] == true)\n            missed += 1\n        end\n        result[idx] = missed\n        idx = parents[idx]\n    end\nend\n\ndef smallest_missing_value_subtree(parents, nums)\n    \n    result = Array.new(nums.length, 1)\n    missed_map = Array.new(100000, false)\n    return result if !nums.include?(1)\n    \n    children_list = create_children_adjacency_list(parents, nums)\n    \n    find_first_missed_number(nums, missed_map, children_list, result, parents)\n    \n    return result\nend\n```\n\nThis solution is inspired from [@lee215](https://leetcode.com/lee215) Solution : [here](https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/discuss/1458486/Python-Strict-O(n)-Solution)
['Ruby']