Write labels on edges with a complex tree implementation

Question

I'm breaking my mind to find an answer with documentation but I have some difficulties,

I asked a question to make a complex tree-like the following and now I'm working on the base implementation to make some customization, in particular, I want to add some label on the red and green arrow because I want indicate the value that is returning the function on the tree, but I'm no able to customize the solution with this feature.

In addition, I want to add some label on the right with the name of the array, like the following picture

This is my actual implementation

\documentclass[12pt, margin=3mm]{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta,
                backgrounds,
                fit}

\begin{document}
    \begin{forest}
        for tree = {
        % nodes
            circle, draw, fill=gray!30,
            minimum size=1.5em, inner sep=0pt, outer sep=0pt,
        /tikz/every label/.style = {font=\tiny},
        /tikz/FIT/.style = {draw, very thick, rounded corners, fill=gray!30,
                            inner sep=4pt, inner ysep=8pt, yshift=-4pt,
                            fit=#1},
        % tree
        /tikz/every edge/.style={draw, -Straight Barb, 
                                 -Straight Barb, shorten >=3pt, shorten <=3pt,
                                 bend angle = 15},% style for bended arrows
            edge=semithick,
            l sep=4mm,
            s sep=12mm,
            where level=3{l sep=11mm}{},% at level 3 increase l sep
            where level=4{no edge, very thick, fill=white}{},
            where level=5{no edge, very thick, fill=white}{},
                    }% level 4 is the lowest
        [1, label=below:{1:[0,7]},  name=t0
            [1, label=below:{2:[0,3]},  name=t11
                [2, label=below:{[0,1]},  name=t21
                    [2, thick, label=below:{[0,0]}
                        [2, label=below:0, name=n0
                            [0, label=below:0] 
                        ]
                    ]
                    [4, label=below:{9:[1,1]}, name=t31
                        [4, label=below:1
                            [0, label=below:1] 
                        ] 
                    ]
                ]
                % to paint the node I can use draw=none,fill=gray, 
                [1, label=below:{5:[2,3]}
                    [3, label=below:{10:[2,2]}
                        [3,  label=below:2
                            [0, label=below:2] 
                        ]
                    ]
                    [1, label=below:{11:[4, 4]}
                        [1, label=below:3
                            [0, label=below:3] 
                        ]
                    ]
                ]
            ]
            [5, very thick,edge=thick, label=below:{3:[4,7]}, name=t62
                [6, thick,edge=thick, name=t61
                    [6, thick,edge=thick,
                        [6, label=below:4
                            [0, label=below:4] 
                        ]
                    ]
                    [7, very thick,edge=thick, name=t6
                        [7, label=below:5, name=n6
                            [0, label=below:5] 
                        ]
                    ]
                ]
                [8, very thick,edge=thick, name=t81
                    [8, very thick,edge=thick, 
                        [8, label=below:6, name=n7
                            [0, label=below:6] 
                        ]
                    ]
                    [10, very thick,edge=thick, name=t7
                        [10, label=below:7, name=n8
                            [0, label=below:7] 
                        ]
                    ]
                ]
             ]
        ]
        \scoped[on background layer]
        \node[FIT=(n7) (n8)] {};
        \draw[color=red]
            (t0) edge [bend right] (t62) 
            (t62) edge [bend right] (t81)
            (t81) edge [bend right] (t7);
        \draw[color=green]
            (t7) edge [bend right] (t81) 
            (t81) edge [bend right] (t62)
            (t62) edge [bend right] (t0);
    \end{forest}
\end{document}

Answer 1

Labeling of bended arrows can be simple done by using quotes library (see MWE below), for example:

    \draw[color=red]
        (t0)  edge [bend right, "a"] (t62)
        (t62) edge [bend right, "b"] (t81)
        (t81) edge [bend right, "c"] (t7);

Edge quotes style you can define as:

/tikz/every edge quotes/.style={auto=right,
                                font=\scriptsize, inner sep=1pt},% style for bended arrows quotes

If you like to have different style, just change above definition accordingly.

Unfortunately it is not clear what you mean with "I want to add some label on the right with the name of the array, like the following picture" Please clarify this. Where is this array, what is in this aray? In generally you can add them in some new node, for example:

\node[right=1em] at (<coordinate>)
    {Lazy[]=\begin{tabular}{|*{6}{c|}}
             \hline
             0 & 0 & 0 & 0 & 4 & 4 \\
             \hline
             \end{tabular}};

Edit:

Temporary I add label "laty[ ] = " left of bottom levels (4 an 5) of diagram.

MWE:

\documentclass[12pt, margin=3mm]{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta,
                backgrounds,
                calc,
                fit,
                positioning,
                quotes}

\begin{document}
    \begin{forest}
for tree = {
% nodes
    circle, draw, fill=gray!30,
    minimum size=1.5em, inner sep=0pt, outer sep=0pt,
/tikz/every label/.style = {font=\tiny},
/tikz/FIT/.style = {draw, very thick, rounded corners, fill=gray!30,
                    inner sep=3pt, inner ysep=7pt, yshift=-3.5pt,
                    fit=#1},
% tree
/tikz/every edge/.style={draw, -Straight Barb,
                         shorten >=3pt, shorten <=3pt,
                         bend right = 15},% style for bended arrows
/tikz/every edge quotes/.style={auto=right,
                                font=\scriptsize, inner sep=1pt},% style for bended arrows quotes
    edge=semithick,
    l sep=4mm,
    s sep=12mm,
    where level=3{l sep=11mm}{},% at level 3 increase l sep
    where level=4{no edge, very thick, fill=white}{},
    where level=5{no edge, very thick, fill=white}{},
            }% level 4 is the lowest
%%%% tree body
    [1, label=below:{1:[0,7]},  name=t0
        [1, label=below:{2:[0,3]},  name=t11
            [2, label=below:{[0,1]},  name=t21
                [2, thick, label=below:{[0,0]}
                    [0, label=below:0, name=n40
                        [0, label=below:0, name=n50]
                    ]
                ]
                [4, label=below:{9:[1,1]}, name=t31
                    [4, label=below:1
                        [0, label=below:1]
                    ]
                ]
            ]
            % to paint the node I can use draw=none,fill=gray,
            [1, label=below:{5:[2,3]}
                [3, label=below:{10:[2,2]}
                    [3,  label=below:2
                        [0, label=below:2]
                    ]
                ]
                [1, label=below:{11:[4, 4]}
                    [1, label=below:3
                        [0, label=below:3]
                    ]
                ]
            ]
        ]
        [5, very thick,edge=thick, label=below:{3:[4,7]}, name=t62
            [6, thick,edge=thick, name=t61
                [6, thick,edge=thick,
                    [6, label=below:4
                        [0, label=below:4]
                    ]
                ]
                [7, very thick,edge=thick, name=t6
                    [7, label=below:5, name=n6
                        [0, label=below:5]
                    ]
                ]
            ]
            [8, very thick,edge=thick, name=t81
                [8, very thick,edge=thick,
                    [8, label=below:6, name=n7
                        [0, label=below:6]
                    ]
                ]
                [10, very thick,edge=thick, name=t7
                    [10, label=below:7, name=n8
                        [0, label=below:7]
                    ]
                ]
            ]
         ]
    ]
    \node[left=4 mm of $(n40)!0.5!(n50)$] {Lazy[ ] = }; % <---   
    \scoped[on background layer]
    \node[FIT=(n7) (n8)] {};
    \draw[color=red]
        (t0)  edge ["a"] (t62)
        (t62) edge ["b"] (t81)
        (t81) edge ["c"] (t7);
    \draw[color=green]
        (t7)  edge ["1"] (t81)
        (t81) edge ["2"] (t62)
        (t62) edge ["3"] (t0);
\end{forest}
\end{document}

or you would like this (code is no present yet):

Answer 2

        (t0) edge [bend right]node[below, ]{\scriptsize below} (t62) 

or

        (t0) edge [bend right]node[fill=white, sloped ]{\scriptsize below} (t62) 

or

(t0) edge [bend right]node[draw=none, fill=white,  sloped, pos=0.7 ]{\tiny below} (t62)