Check if each internal node of a BST has exactly one child
Given Preorder traversal of a BST, check if each non-leaf node has only one child. Assume that the BST contains unique entries.
Examples
Input: pre[] = {20, 10, 11, 13, 12}
Output: Yes
The give array represents following BST. In the following BST, every internal
node has exactly 1 child. Therefor, the output is true.
20
/
10
\
11
\
13
/
Let me know if my algo is wrong.
ReplyDeleteStep 1: Store the pre order traversal in an array A[].
A[0] represent the root of the BST.
Step 2: Start from i = 0. Compare A[i] with A[i+1]
if A[i] > A[i+1]
then for each j > i, A[i] > A[j]
else
A[i] < A[j], for all j in-range[i+1, n]
Step 3: repeat Step 2 for all i belongs to 0, n-2