How handle the add of a new feature to the dataset?
What you ask for is known as Transfer Learning in the Machine Learning framework, so you might want to look more into that direction.

An interesting publication regarding Transfer Learning in Decision Trees is this.