LC: Verify Preorder Sequence in Binary Search Tree - spiralgo/algorithms GitHub Wiki
Verify Preorder Sequence in Binary Search Tree
The Essence:
The pre-order traversal has two consequences:
- If a value is assumed to be the left child of some previous value, then all the values larger than the parent value can't be assumed to belong to this part of the tree. They should be the parent's right child. This parent needs to be the largest value smaller than this new value.
- If a value is assumed to be the right child of some previous value, then all the values are bounded by below by this parent value.
These consequences imply that the sequence values are always bounded either from below or above. In case of mismatches, the procedure should backtrack to some value to take appropriate action.
Details:
The results mentioned above can be turned into a practical algorithm by using stacks. The stacks pop and be pushed depending on the array. The minimum boundary value should also be kept as a number. The input array can also be used as a stack.
Further detailed explanation can be found at: https://github.com/spiralgo/algorithms/pull/318