After each operation the pre-order remain unchanged, so for a right son, it change its father to 1 step backward. If you cannot do that, puts 0. For a left son, you can assign arbitrary steps less than k for it to “climb up” the chain. So the problem is reduced to given some intervals(right sons) and you can add new intervals(left sons).