treeExplainer algorithm intuition
The paper you refer to actually states the following intuition:


  Algorithm 1 estimates $E[f(X)|do(X_S = x_S )]$ by recursively following the decision path for $x$ if the split feature is in $S$, and taking the weighted average of both branches if the split feature is not in $S$.


It seems to be a slight modification of the original description in arxiv 1706.06060:


  For a tree model $E[f(x) | x_S]$ can be estimated  recursively using
  Algorithm 1, where $v$ is a vector of node values, which takes the value
  $internal$ for internal nodes. The vectors $a$ and $b$ represent the left
  and right node indexes for each internal node. The vector $t$ contains
  the thresholds for each internal node, and $d$ is a vector of indexes of
  the features used for splitting in internal nodes. The vector $r$
  represents the cover of each node (how many data samples fall in that
  subtree).


I presume $S$ is an item in the set of all subsets of N features.