In things like this, it's often easier to think backwards, so first consider what you need. From your description, let's list them:
- Recursion
- Validity
- Count of complete nodes
OK, that's a fairly short list, this should be manageable. Let's start with an empty method and I'll add description of what should be happening.
valid_bst () {
}
Now validity. How do you check for validity? In chat you said a tree is valid "if ... all left children are less than the parent, and right children are greater than the parent." I'm sure you meant to allow equality as well. That would be t.left.value <= t.value <= t.right.value
.
valid_bst () {
This node is valid if t.left.value <= t.value <= t.right.value
}
But what if one of the children is missing? From what you've said, I believe you know the node is still valid if one is (or both are) missing. Let's add this, restructuring slightly:
valid_bst () {
This node is valid to the left if
there is no left child or
it is no greater than the current node.
This node is valid to the right if
there is no right child or
it is no less than the current node.
This node is valid overall if it is valid to the left and right.
}
OK, we now know whether this node is valid. How do we check whether the entire tree is valid? It's not in an array, so we probably can't/don't want to loop over it linearly. Your assignment gives the answer: recursion. But how do we accumulate an answer using recursion? We have access to three pieces of information, whether this node is valid, and the result of calls asking whether the left and right nodes are valid. Obviously the tree is only valid if all three of those are true.
valid_bst () {
This node is valid to the left if
there is no left child or
it is no greater than the current node.
This node is valid to the right if
there is no right child or
it is no less than the current node.
This node is valid overall if it is valid to the left and right.
Is the left child valid?
Is the right child valid?
This tree is only valid if this node and both its children are.
}
If you're paying attention, that even tells us what our function needs to return.
Now, how do we integrate the counting? You say what counts ("a parent node with both left and right children nodes"), and that shouldn't be hard to translate into actual code. Check whether that condition is satisfied and increment the counter appropriately. Just remember this has to be somewhere where it will be reached every time it is true.
And of course I've left out some details like the recursion stopping condition and checks for null.
<
defined on nodes? $\endgroup$true
orfalse
? $\endgroup$