Constructing multi-level object tree with manual dependency injection

I am working on refactoring a Java application that I wrote. At the time of writing the original, I made some poor design decisions, and am now suffering the consequences. In particular, the code is nearly impossible to unit test, and dependencies are all over the place.

I have been doing a lot of reading about design patterns and good OO-design principles (including SOLID). I think the key to solving my problems lies in the following: constructor dependency injection (ideally NOT via a framework like Spring; I'd rather stick to plain old Java), factories, builders, and good OO-design in general.

Without getting into too many specifics, imagine I have an object structure where O1 has one or more O2 child objects, and each O2 object has one or more O3 child objects, and so on. So, essentially, O1 is a parent of O2, and O2 is a parent of O3. (But not in the inheritance sense.)

The dependencies I want to represent are of the child to the parent. So, for example, injecting the dependencies into the constructor might result in something like this:

// highest-level object; no dependencies
O1 o1a = new O1();

// second-level objects; depend on highest-level object
O2 o2a = new O2(o1a);
O2 o2b = new O2(o1a);

// 3rd-level objects; depend on second-level objects
O3 o3a = new O3(o2a); // dependency on o2a
O3 o3b = new O3(o2a); // dependency on o2a
O3 o3c = new O3(o2b); // dependency on o2b

OK, so that in itself is simple enough. But there are some complicating factors:

• Each of these objects is potentially quite complex to construct (some involve the parsing of schemas and the building of in-memory object models associated with the objects);
• I won't know at compile time how many of each object will be required (this is configuration dependent); as such, manually coding dependencies (as above) is not an option;
• I don't want to "new" specific classes, because I want the code to be extensible, and want to be able to "stub" in different versions for testing; (factories?);
• I need to be able to start the creation process at the "lowest level"; for example, I may know at run-time that I need to create a specific O3 object; to do this requires determining O3's "parent" (O2), and then O2's parent (O1), then creating O1, creating O2 (injecting newly-created O1), creating O3 (injecting newly-created O2), etc.
• I might also, potentially, want to keep track of objects so that they can be reused; so, in the example above, o3a and o3b both make use of o2a; if o2a was created in the course of creating o3a, I'd want to reuse the same object when creating o3b.

In all my reading of design patterns, unfortunately, I have never seen any example of how to accomplish something even vaguely like this. (All examples are quite simple by comparison.)

I have wondered about creating some sort of factory or builder for O3, and passing it an instance of a factory or builder for O2. That instance of O2 factory or builder would, in turn, have been created with an instance of a factory or builder for O1. But I'm not sure if this is the right approach, and even if it is, I'm struggling to get much beyond the high-level concept.

I would greatly appreciate some guidance on how to accomplish all of this in a clean, maintainable, extensible way. It's a bit of a tall order, I know.

Thanks in advance,
Greg