Search algorithm for a binary search tree.

[hassan_]

Hi everyone, hope everything is going good? , I just sat a Data Structures and Algorithms exam paper today, it went pretty good, however I wanted to get a few things straight and to help me further understand some concepts. Can anyone help me with question below.

The exam question was the very final question and it goes as follows:

Write a recursive search method that goes through a binary search tree, searching for an element at node p, if the node p is found in the tree return true, else return false.

I don't have the exam paper they took it away but that is how I remember the question. My answer was as follows:

Boolean search(Tree tree, TreeNode p){
	If(tree.TreeRoot == null){
		return false;
	}
	If(p < tree.TreeRoot){
		search(tree.left, p);
		If(p == el){
			return true;
		}
	}
	If(p > tree.TreeRoot){
		search(tree.right, p);
		If(p == el){
			return true;
		}
	}
	return false;
}

PS: el is the element.

Hopefully you guys can give me helpful tips in improve the way I go about writing algorithms and show where I've gone wrong, and what I need to change etc.

Thanks,

Hass

[pm_kirkham]

As written above, neither the value of p or el change during the algorithm, and you don't look at the value returned by the recursive calls to search, so it's the same as:

Boolean search(Tree tree, TreeNode p){
	If (tree.TreeRoot == null)
		return false;
	
	If (p != tree.TreeRoot)
		return (p == el);
	
	return false;
}

Normally you recurse on nodes, rather than the tree, (though not having seen the paper you may have a tree made up of trees), and look for a value. But you are making roughly the right recursive sequence of calls, so it's not all bad.

[hassan_]

Hmm, I think I was automatically assuming that each tree match have a subtree, if TreeRoot != null. But maybe my implementation is wrong? I'm still an ammateur at writing recursive algorithms lol

[pm_kirkham]

Maybe, but there's no way for me to know that the variable called 'tree root' is meant to be a sub-tree rather than the tree's root. You also aren't recursing into 'tree root', but into left and right branches, which appear to be of type tree (making it a tree of trees).

On the other hand, you pass in a 'Tree' and a 'TreeNode', which implies that there's a difference between a tree and a node. Usually 'node' denotes a vertex in a tree, and may have implicit or explicit edges from it (either the node type has a left and right member variable for the sub trees like your 'Tree' type, or there's some other mechanism for getting the left and right members, such as in a array implementation of a Heap).