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

Problem Detail: 

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?

Asked By : OghmaOsiris

Answered By : Gilles

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/105