# Traverse tree collecting nodes combinations

Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts.

Parts can be required - every build must contain them.

Parts can be optional.

Parts can conflict with other parts.

Parts can have optional parts inside them.

Example tree:

Car
| - Motor (required)
| - - V8
| - - V12
| - - - Colour (optional)
| - - - - Black
| - - - - Chrome
| - Transmission (required)
| - - Mechanical
| - - Automatic
| - Wheels (optional)
| - - Basic
| - - Fancy
| - - - Colour (optional)
| - - - - Red
| - - - - Blue
| - BodyStyle (optional)
| - - Hatchback (conflicts with Motor.V12)
| - - Buggy (conflicts with Motor.V8)


Valid builds for this tree:

Car | Motor.V8 | Transmission.Automatic
Car | Motor.V8 | Transmission.Automatic | Wheels.Basic
Car | Motor.V12.Colour.Black | Transmission.Automatic | Wheels.Basic
Car | Motor.V8 | Transmission.Automatic | BodyStyle.Hatchback
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy | BodyStyle.Buggy
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy.Colour.Red | BodyStyle.Buggy


What algorithm should I look for, that can solve this task

• Can you edit your question to ask a more specific question? I don't understand what you are asking. – D.W. Sep 16 '19 at 2:01
• @D.W. I am looking for a suitable algorithm, that can generate me all permutations or nodes of a tree, filtering results by provided rules – Neonailol Sep 16 '19 at 5:29
• Use exhaustive search. – Yuval Filmus Sep 16 '19 at 7:44