Now there is a problem with „Choose-your-own-adventure“-style branching stories: the complexity grows with every decision the player can make. It is clearly impossible to create something like an open world or to visit different locations at the player’s whim with branching elements. A large studio can do it, like Quantic Dream did with Heavy Rain, but it is always limiting.
The answer is a web instead of a tree. We need locations, that are interconnected and can be traversed by the player back and forth. Like this, the player can visit a vast number of locations in an order, that he likes. But this is lacking the actual decision making and the progression.
So what we need is combine the two approaches. The player must be able to change the locations with the actions he takes there. He might even be able to change the location in one or more ways, as his decisions dictate. Each location represents its own branching decision tree in a way, but can be visited and abandoned in more than one of those states. The decisions and events in one location can even affect the states of other locations.
This approach is expandable as well. The player character can have his own stats, that can be changed by triggering certain events in locations. He can learn new skills, he can improve his abilities, he can earn a reputation that might open some doors elsewhere. Of course he can find loot, new weapons, armor and trinkets, that give him more power or new abilities. He could even gather followers, other adventurers to travel with him on their way to glory.
This way, we get a world, that can be explored and that can be played with, and that can be expanded easily, when the story demands it, with a set of a few simple systems. But the player ist still caught on a preset path, like in a labyrinth, that he can only explore, but not leave a mark on by choosing his own approach.