I do not completely understand your idea.
2) I create the new entities in the Database.
What entries do you create? How are they related to FlyTreeView nodes?
3) I reload the FlyTreeView from the Database.
I think that in this place you can load only expanded part of the treeview. Other nodes can use PopulateOnDemand
4) I recursively search for the FlyTreeNode that I want to be selected.
Do you need to restore previously selected node. Or what is the criteria for the search?
I believe there's always an option to use load-on-demand in various cases. Your one does not look like exception.