(about the Java solution) Isn't there a condition missing for the Return null statements?


#1

It seems to me that the editorial solution provided in Java lacks a stop condition: I feel that in certain situations the execution should pass by a return null; statement but when I try to “run” it manually that does not seem to be the case. So the solution does not work in paper for me.

The example I’m working on is the following tree:
11
/
2 13
/ \
1 9 57
/ / \
3 25 90
/
17

The sequences of nodes for the two types of traversals are:

  • in order: 1, 2, 3, 9, 11, 13, 17, 25, 57, 90
  • pre order: 11, 2, 1, 9, 3, 13, 57, 25, 17, 90.

At some point, if I follow the editorial solution, the node 13 seems to be inserted as a left child of node 3. That is incorrect.
I attach a photo of the execution I was trying to follow, in case you can follow it and help me.

I think the correct behaviour of the program there would be to return null, but that does not happen as the call seems to be:
root.left (where root is node 3) = root.left = buildTree(pre, new ArrayList<>(in.subList(0, idx))); with idx=2,
that is: in.subList(0, 2) . That contains 2 elements (indexes 0, 1) so we don’t return null through condition:
if (pre.isEmpty() || in.isEmpty()) {return null;}

and we also don’t return null through the condition:
if (rIdx > pre.size()) {return null;}
because at that point, rldx was 4 and pre.size() is always 10, no? So this condition will never be true and we never return null through here anyway. It is totally useless, isn’t it? Is there a mistake?