Implementing recursive delete for Radix trie

[hydradon]

I have the following Radix trie structures:

struct Node {
    node_map: HashMap<char, Node>,
    value: Option<i32>,
}

struct RadixTrie {
    root: Node,
}

I am attempting to implement the delete function: delete(&mut self, key: &String) -> Option<i32>
However, I can't seem to arrive at the correct recursion. I know that I have to travel to the leaf node and delete backward. So if I have a key "Foobar", I have to traverse to "r" node and delete backward, and return the value at "r"

Could you help?

[Michael-F-Bryan]

Are you looking for something like this?

use std::collections::HashMap;

struct Node {
    node_map: HashMap<char, Node>,
    value: Option<i32>,
}

struct RadixTrie {
    root: Node,
}

impl Node {
    pub fn delete(&mut self, key: &str) -> Option<i32> {
        let first_char = key.chars().next()?;
        
        let rest = &key[first_char.len_utf8()..];
        
        if rest.is_empty() {
            // last character, need to delete
            let removed = self.node_map.remove(&first_char)?;
            removed.value
        } else {
            // otherwise, recurse
            let node = self.node_map.get_mut(&first_char)?;
            node.delete(rest)
        }
    }
}

impl RadixTrie {
    pub fn delete(&mut self, key: &str) -> Option<i32> {
      self.root.delete(key)  
    }
}

EDIT: Sorry if I've spoiled things by providing an answer instead of just pointing you in the right direction! It looked like a nice little challenge and I wanted to see if I could figure out the recursion for myself.

[pcpthm]

This code is incorrect.

1. It removes all nodes with prefix matches. Consider remove([("ab", 1)], "a").
2. Probably you want to remove a node when all descendants are removed. The code above leaves all empty nodes.