Maintaining state while walking a tree structure
At first step I've removed hardcoded into function input data, so it's become testable.
   ...
   walkImpl (Children [Value 1; Value 2 ; Children [Value 9; Children [Value 4; Value 5]; Value 9]])
    
walk ()


let walk n =
    ...
    walkImpl n

walk (Children ...)

Than get rid of type which exists only for one function and replaced it with anonymous record.
    let initialState = {| oneFound = false; fourFound = false |}

Afterwards comes hardest part of refactoring: remove mutability. In order to use mutable state in functional way we have to use recursion and pass state as parameter to function which must return updated state, so signature should be State -&gt; State instead of () -&gt; () (curNode omitted for clarity).
      | Value n -&gt;
            let patched =
                match n with
                | 1 -&gt; {| state with oneFound = true |}
                | 4 -&gt; {| state with fourFound = true |}
                | 9 -&gt;
                    if state.oneFound &amp;&amp; state.fourFound then
                        printfn &quot;Found a good 9&quot;
                    else
                        printfn &quot;Found a bad 9&quot;
                    state
                | _ -&gt; state
            printfn &quot;Node value %d&quot; n
            patched

Now we have part of function that matches over curNode and transforms state if Value branch is evaluated. We also must transfer state when walking across different children while iterating list. List.fold is function that iterates over list while keep tracking of state changes. All list function may be implemented with fold, such a powerful abstraction.
        | Children c -&gt; c |&gt; List.fold walkImpl state

Now we have complete working example without mutations
type N = Value of int  | Children of N list

let walk n =
    let rec walkImpl (state : {| oneFound: bool; fourFound: bool |}) curNode = // explicit type required here
        match curNode with
        | Value n -&gt;
            let patched =
                match n with
                | 1 -&gt; {| state with oneFound = true |}
                | 4 -&gt; {| state with fourFound = true |}
                | 9 -&gt;
                    if state.oneFound &amp;&amp; state.fourFound then
                        printfn &quot;Found a good 9&quot;
                    else
                        printfn &quot;Found a bad 9&quot;
                    state
                | _ -&gt; state
            printfn &quot;Node value %d&quot; n
            patched
        | Children c -&gt;
            c |&gt; List.fold walkImpl state

    let initialState = {| oneFound = false; fourFound = false |}
    walkImpl initialState n
    |&gt; ignore // don't care about state, because it's for internal use only

[&lt;EntryPoint&gt;]
let main argv =
    walk (Children [Value 1; Value 2 ; Children [Value 9; Children [Value 4; Value 5]; Value 9]])
    0