Algorithm to test whether a binary tree is a search tree and count complete branches

Question

I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with an assumed global counting variable. This is an assignment for my data structures class.

So far I have

void BST(tree T) {
   if (T == null) return
   if ( T.left and T.right) {
      if (T.left.data < T.data or T.right.data > T.data) {
        count = count + 1
        BST(T.left)
        BST(T.right)
      }
   }
}

But I can't really figure this one out. I know that this algorithm won't solve the problem because the count will be zero if the second if statement isn't true.

Could anyone help me out on this one?

Answer 1

As others have already indicated in comments, you really have two unrelated functions here: testing whether the tree is a search tree, and counting the complete branches. Unless the assignment specifically calls for it, I would write two separate functions.

Let's see abount counting the complete branches first. That means counting the nodes that have both a left child and a right child. Then you need to increment the counter (count = count + 1) when both T.left and T.right are non-null (not T.left.data and T.right.data: the data doesn't matter for this task).

if (T.left and T.right) {
    count = count + 1

Furthermore, you need to explore the left subtree even if the right subtree is empty, and you need to explore the right subtree even if the left subtree is empty. So watch where you put the recursive calls.

To test whether the tree is a search tree, you need to inspect the data values. You've already got something close to the right comparison; not quite right. Write a few example trees with various shapes (not very big, 2 to 5 nodes) and run your algorithm on them to see what happens.

You still need to find some place to put the result of the validity check. Again, watch where you put the recursive calls (if you only do this part, there are several solutions, but at this stage don't worry if you only see one).

Finally, once you've managed to write both functions separately, and you've tested them on a few examples, put them together carefully (if required by the assignment).

Answer 2

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.

Answer 3

My three comments above are three hints to problems with your code.

1. Unless you have already specifically defined how a compare operator should handle the node data type, most likely comparing two nodes directly won't do what you want. What you probably meant was to compare the fields stored in the nodes, for example node1.value < node2.value
2. right now, you're only adding to the count if the third if is true, are you sure that's what you meant to do? By the way, you may want to double check that that if statement does what you want.
3. I assume that you want to return true if the tree is a valid BST and false otherwise. Which means that you have to always return true or false in a base case, and you should be returning the results of your recursive calls as well.