Java Relationship between interfaces/abstract classes

I am trying to build an algorithm that works in different ways depending on a traversal strategy and an update strategy. However, not every update Strategy works with every traversal strategy. Hence, I figured that an update strategy must only be instantiated with a corresponding traversal strategy. I wanted to force a constructor for that (see below). So that the subclasses would have to check if they support the strategy.

I am currently having an Interface

public interface TraversalStrategy {
...
}

And an (invalid) abstract class

public abstract class UpdateStrategy {
protected TraversalStrategy travStrategy;

public abstract UpdateStrategy(TraversalStrategy travStrategy);
}

What is the correct way to imply such a dependency? I could of course add an empty body to this constructor but that seemed wrong to me.

I am sure there has been questions asking similar things but I don't really know how to describe this correctly. Hence it is hard for me to find the right answer. I checked the following questions that didn't help me much:

Relationship between Interfaces and Abstract Data Type in Java

Abstract classes and interfaces in Java

Can an abstract class have a constructor?