Я бы предложил использовать рекурсивность.
Конечно, это пример, и вам нужно будет удалить объявление myTree и использовать свое дерево, но это поможет вам начать.
private void replaceInTreeView()
{
TreeView myTree = new TreeView();
ReplaceTextInAllNodes(myTree.Nodes, "REPLACEME", "WITHME");
}
private void ReplaceTextInAllNodes(TreeNodeCollection treeNodes, string textToReplace, string newText)
{
foreach(TreeNode aNode in treeNodes)
{
aNode.Text = aNode.Text.Replace(textToReplace, newText);
if(aNode.ChildNodes.Count > 0)
ReplaceTextInAllNodes(aNode.ChildNodes, textToReplace, newText);
}
}
}