that far from a tree, but how about this

import copy

mydata = {1000024: [[0.7, [1000022, 11, -12]], [0.3, [1000022, 2, -1]]], 
          1000021: [[0.6, [1000024, 1, -2]], [0.4, [1000022, 21]]]}

def prob_tree(data,ini,prob=1):
    data=copy.deepcopy(data)
    val=data.pop(ini,None)
    if val:
        for lst in val:
            if lst[1][0] in data:
                extra=lst[1][1:]
                for x in data[lst[1][0]]:
                    x[1].extend(extra)
                prob_tree(data,lst[1][0],lst[0])
            else:
                print( prob*lst[0],lst[1])

prob_tree(mydata,1000021)

output

0.42 [1000022, 11, -12, 1, -2]
0.18 [1000022, 2, -1, 1, -2]
0.4 [1000022, 21]

EDIT

In a inspiration struck and the use of a little of functional style here is the new version

import itertools, functools

def partition(pred, iterable):
    'Use a predicate to partition entries into false entries and true entries'
    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9
    # Direct from the recipes in itertools documentation
    t1, t2 = itertools.tee(iterable)
    return itertools.filterfalse(pred, t1), filter(pred, t2)


def prob_tree(data,ini) -> (float,tuple):
    """Generator of all end points of the probability tree contained 
       in data, starting with ini"""
    for prob,path in data[ini]:
        no_more,more = map(tuple,partition(lambda x: x in data, path))
        if more:
            for node in itertools.product( *[prob_tree(data,x) for x in more] ):
                new_prob,new_path = functools.reduce(lambda acum,new: (acum[0]*new[0],acum[1]+new[1]),node,(prob,tuple()))
                yield new_prob, no_more + new_path
        else:
            yield prob, no_more

mydata = {1: [[.9, [2,3]], [.1, [4,5]]],
          4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]],
          5: [[.4, [13,14]], [.6, [15,16]]]
          }

mydata2 = {1: [[.8, [2,3]], [.1, [4,5]],[.05, [2,4]],[.05,[5,6]] ],
          4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]],
          5: [[.4, [13,14]], [.6, [15,16]]]
          }

mydata3 = {1: [[.8, [2,3]], [.1, [4,5]],[.05, [2,4]],[.05,[5,6]] ],
          4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]],
          5: [[.4, [13,14]], [.6, [15,16]]],
          13:[[.58,[23,32]],[.42,[42]] ], 
          16:[ [.9,[17,18]], [.1,[20,21]] ],
          }

output

>>> for x in prob_tree(mydata,1):
    print(x)


(0.9, (2, 3))
(0.008000000000000002, (6, 7, 13, 14))
(0.012000000000000002, (6, 7, 15, 16))
(0.020000000000000004, (8, 9, 13, 14))
(0.03, (8, 9, 15, 16))
(0.012, (10, 11, 12, 13, 14))
(0.018, (10, 11, 12, 15, 16))
>>> 
>>> 
>>> for x in prob_tree(mydata2,1):
    print(x)


(0.8, (2, 3))
(0.008000000000000002, (6, 7, 13, 14))
(0.012000000000000002, (6, 7, 15, 16))
(0.020000000000000004, (8, 9, 13, 14))
(0.03, (8, 9, 15, 16))
(0.012, (10, 11, 12, 13, 14))
(0.018, (10, 11, 12, 15, 16))
(0.010000000000000002, (2, 6, 7))
(0.025, (2, 8, 9))
(0.015, (2, 10, 11, 12))
(0.020000000000000004, (6, 13, 14))
(0.03, (6, 15, 16))
>>> 
>>> 
>>> 
>>> for x in prob_tree(mydata3,1):
    print(x)


(0.8, (2, 3))
(0.004640000000000001, (6, 7, 14, 23, 32))
(0.003360000000000001, (6, 7, 14, 42))
(0.010800000000000002, (6, 7, 15, 17, 18))
(0.0012000000000000001, (6, 7, 15, 20, 21))
(0.0116, (8, 9, 14, 23, 32))
(0.008400000000000001, (8, 9, 14, 42))
(0.027000000000000003, (8, 9, 15, 17, 18))
(0.003, (8, 9, 15, 20, 21))
(0.006959999999999999, (10, 11, 12, 14, 23, 32))
(0.00504, (10, 11, 12, 14, 42))
(0.0162, (10, 11, 12, 15, 17, 18))
(0.0018, (10, 11, 12, 15, 20, 21))
(0.010000000000000002, (2, 6, 7))
(0.025, (2, 8, 9))
(0.015, (2, 10, 11, 12))
(0.0116, (6, 14, 23, 32))
(0.008400000000000001, (6, 14, 42))
(0.027000000000000003, (6, 15, 17, 18))
(0.003, (6, 15, 20, 21))
>>> 

EDIT 2 adding check for circular references

def prob_tree_with_check(data,ini,visited=frozenset()):
    """Generator of all end points of the probability tree contained 
       in data, starting with ini. Check if a previously visited branch
       of the tree is visited again and raise RuntimeError in that case"""
    if ini in visited:
        raise RuntimeError("Branch allready visited: %r"%ini)
    visited = visited.union((ini,))
    for prob,path in data[ini]:
        no_more,more = map(tuple,partition(lambda x: x in data,path))
        if more:
            for node in itertools.product( *[prob_tree_with_check(data,x,visited) for x in more] ):
                new_prob,new_path = functools.reduce(lambda acum,new: (acum[0]*new[0],acum[1]+new[1]),node,(prob,tuple()))
                yield new_prob, no_more + new_path
        else:
            yield prob, no_more

mydata_bad = {1: [[.9, [2,3]], [.1, [4,5]]],
          4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]],
          5: [[.4, [13,14]], [.6, [15,16,1]]] # <-- try to go back to 1
          }

output

>>> for x in prob_tree_with_check(mydata_bad,1):
    x


(0.9, (2, 3))
Traceback (most recent call last):
  File "<pyshell#35>", line 1, in <module>
    for x in prob_tree_with_check(mydata_bad,1):
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 137, in prob_tree_with_check
    for node in itertools.product( *[prob_tree_with_check(data,x,visited) for x in more] ):
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 137, in prob_tree_with_check
    for node in itertools.product( *[prob_tree_with_check(data,x,visited) for x in more] ):
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 132, in prob_tree_with_check
    raise RuntimeError("Branch already visited: %r"%ini)
RuntimeError: Branch already visited: 1
>>>           

It's more like a probability graph than a tree, but that depends on how you define a state (a node in the graph). The code below defines "a state" as the tuple of integers that can still be chosen. The great advantage is that there are only 16 possible states then (depending on which subset of {1, 2, 3, 4} has already been picked), and the fewer the states the faster this goes.

The disadvantage is that having so few possible states constrains questions that can be answered. For example, no state records whether a 5 has ever been picked. But I don't know what you meant by "etc.", and both your description and your code only asked about prob_to_find_one and prob_to_find_both, The states used here are sufficient to answer those.

def crunch():
    from fractions import Fraction
    from collections import defaultdict

    step = 0
    state2prob = {tuple(range(1, 9)) : Fraction(1)}
    while True:
        step += 1
        new_state2prob = defaultdict(Fraction)
        for state, prob in state2prob.items():
            nchoices = len(state)
            for choice in state:
                newstate = state
                if 1 <= choice <= 4:
                    newstate = list(state)
                    newstate.remove(choice)
                    newstate = tuple(newstate)
                new_state2prob[newstate] += prob / nchoices
        state2prob = new_state2prob
        assert sum(state2prob.values()) == 1
        prob1 = prob12 = Fraction(0)
        for state, prob in state2prob.items():
            if 1 not in state:
                prob1 += prob
                if 2 not in state:
                    prob12 += prob
        print(f"{step=}")
        print(f"    {prob1=} {float(prob1):7.2%}")
        print(f"    {prob12=} {float(prob12):7.2%}")

The output starts like so:

step=1
    prob1=Fraction(1, 8)  12.50%
    prob12=Fraction(0, 1)   0.00%
step=2
    prob1=Fraction(27, 112)  24.11%
    prob12=Fraction(1, 28)   3.57%
step=3
    prob1=Fraction(545, 1568)  34.76%
    prob12=Fraction(115, 1176)   9.78%
step=4
    prob1=Fraction(146201, 329280)  44.40%
    prob12=Fraction(43739, 246960)  17.71%
step=5
    prob1=Fraction(36652993, 69148800)  53.01%
    prob12=Fraction(13765027, 51861600)  26.54%
step=6
    prob1=Fraction(8796724649, 14521248000)  60.58%
    prob12=Fraction(3876980411, 10890936000)  35.60%
step=7
    prob1=Fraction(2047820152657, 3049462080000)  67.15%
    prob12=Fraction(1015122839923, 2287096560000)  44.38%
step=8
    prob1=Fraction(466169430547001, 640387036800000)  72.79%
    prob12=Fraction(252512187968939, 480290277600000)  52.57%
step=9
    prob1=Fraction(104336675177661793, 134481277728000000)  77.58%
    prob12=Fraction(60499089868078627, 100860958296000000)  59.98%

Note that while the Fraction type automatically converts to lowest terms, the numerators and denominators grow large quickly. This is exact rational arithmetic.