Building a linked tree error (stack overflow)

Hi.

There is a data structure that I am developing.

public type Tree<K, V> = {
key: K;
value: V;
var parent: ?Tree<K, V>;
var childs: ?List.List<Tree<K, V>>;
};

public func empty<K, V>(key: K, value: V) : Tree<K, V> { 
    return {
        key=key; 
        value=value; 
        var parent=null; 
        var childs=?List.nil<Tree<K, V>>();
    };
};

public func add_child<K, V>(parent : Tree<K, V>, key: K, value: V){

    var tree : Tree<K, V> = { 
        key=key; 
        value=value; 
        var parent=?parent; 
        var childs=?List.nil<Tree<K, V>>();
    };

    var childs: ?List.List<Tree<K, V>> = parent.childs;
    
    switch(childs){
        case(null){
            Debug.print("errors tree.childs = null");
        };
        case(?childs){
            let b: Bool = List.isNil<Tree<K, V>>(childs);
            switch(b){
                case(true){
                    Debug.print("first add child");
                    parent.childs := ?List.push<Tree<K, V>>(tree, List.nil<Tree<K, V>>());
                };
                case(false){
                    Debug.print("new child");
                    parent.childs := ?List.push<Tree<K, V>>(tree, childs); 
                };
            }; 
        };
    }; 
};

At the first start, an error appears in the tests:

The Replica returned an error: code 5, message: “Canister rrkah-fqaaa-aaaaa-aaaaq-cai trapped: stack overflow”

Test:

public func test(): async(){
var tree = Tree.empty<Text, Text>(empty_key,empty_val);
Debug.print("tree " # debug_show(tree));

    var childs = Tree.get_childs<Text, Text>(tree);
    Debug.print("childs " # debug_show(childs));

    var tree_0 = Tree.add_child<Text, Text>(tree, "key_0", "value_0");
    var childs2 = Tree.get_childs<Text, Text>(tree);
    Debug.print("childs " # debug_show(childs2));
};

What is the reason for this behavior?

Haven’t tested (and am on mobile) but I suspect that debug_show is going into infinite recursion trying to print your cyclic data structure. The parent pointers introduce a cycle.

Try commenting out the debug_show calls to check and, if so, implement your own show for the data structure that skips the parent fields.

1 Like

Thank you for advice. Indeed, the problem is in recursion

Debug.print(“childs” # debug_show(childs));