Starting at the bottom and balancing upward suggests that you up upward links, which otherwise are not required.
The information I store on the way down is precisely the path that was used - a series of "left" or "right" steps. If you have enough linkage information in the tree to determine the path given any node in the tree, then you would not need to store any information.
But isn't having all that extra linkage information a bit of a waste of space?