binary search tree (BST) find method in C#

Question

how can I Write a code with these requirements? this is the question: check if there is a node with key K in the tree T, and if so, return a reference to this node. If the tree is empty, report that the node was not found and stop. Otherwise, compare K with the key value of the root node X.

If K=X, issue a link to this node and stop.
If K>X, recursively search for the key K in the right subtree of T.
If K<X, recursively search for the key K in the left subtree of T.

This is what i found:

public GenBT<T> Find(GenBT<T> k, T inf){ 

if (k == null) return null; 

else 

switch (inf.CompareTo(k.inf)){ 

case 1: return Find(k.RT, inf); 

case -1: return Find(k.LT, inf); 

case 0: return k; 

default: return null;} 

};

but I also found that if I want to search or find in BST I have to use a code like this :

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
    
   while(current->data != data){
    
      if(current != NULL) {
         printf("%d ",current->data);
            
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
            
         //not found
         if(current == NULL){
            return NULL;
         }
      }         
   }
   
   return current;
}

These two look very different and I don't know which way is right and in general what is the right way of solving this question

What have you tried? Some people might like to give you an answer, but most people want to see you have at least tried something. — mikelegg, Dec 14 '20 at 11:34
you didn´t post a **question**, but just what was assigned to **you**. So unless you don´t provide what you´ve tried and where specifically you´re stuck, you won´t get much help here. — MakePeaceGreatAgain, Dec 14 '20 at 11:45
@mikelegg I have added two types of codes I had, thanks for reminding me about it — Mostafa Ghorbani, Dec 14 '20 at 11:59
@HimBromBeere I have added two types of codes I had, thanks for reminding me about it — Mostafa Ghorbani, Dec 14 '20 at 12:00
The first solution is a recursive solution. The second one is an iterative solution. Both are valid, see this for more details: https://stackoverflow.com/questions/15688019/recursion-versus-iteration — JonasH, Dec 14 '20 at 12:01
the most obious to me without diving deep into is that the first seems like C#, while the latter seems like C++. As to "which one is right" it´s pretty simply that one that gets its job done. — MakePeaceGreatAgain, Dec 14 '20 at 12:37
@JonasH, thank you for commenting and sharing that useful link. how can I use the second code to solve this question for finding "k", like what should I replace in that code. what I think is that I should replace `int data` with ` k ` and maybe `root` with `x` I don't know to be honest . — Mostafa Ghorbani, Dec 14 '20 at 13:48
I assume this is schoolwork, so I'm hesitant to just provide a complete solution. Your iterative example is C code, so may be a bit more difficult to read. Consider the recursive method, to make it iterative you will need to insert a loop. When you come to the recursive `Find` call, see if you can remove the call and instead modify the variables to have the same effect as the function call. See also https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration — JonasH, Dec 14 '20 at 15:27
@JonasH yes its is one part of my university project which I'm stuck at )) thank you so much for all this information, it was all very useful — Mostafa Ghorbani, Dec 14 '20 at 15:45
@JonasH the first code that I posted was my friend's code but after searching around and looking at other codes that one looked different from what I saw on youtube and other websites, that's the first reason I posted it here but I'm trying to do it with the second option which you said it is called iterative solution . — Mostafa Ghorbani, Dec 14 '20 at 15:48

JonasH · Accepted Answer · 2020-12-15T07:33:09.310

To transform the recursive solution to an iterative one we need to insert a loop. In the recursive case we change the node parameter for each recursion. To do the same in the iterative case we simply create a variable that is updated instead of doing a recursion.

Changed naming to make a clearer and compilable example. Note also that CompareTo can return any number, not just 0, 1, -1. So a switch is insufficient:

    public class Node<T>
    {
        public Node<T> Left { get; }
        public Node<T> Right { get; }
        public T Value { get; }

        public Node(Node<T> left, Node<T> right, T value)
            => (Left, Right, Value) = (left, right, value);
    }

    public static Node<T> Find<T>(Node<T> root, T target) where T : IComparable<T>
    {
        var current = root;
        while (current != null)
        {
            var comparison = target.CompareTo(current.Value);
            if (comparison > 0) 
                current = current.Right;
            else if (comparison < 0)
                current = current.Left;
            else
                return current;

        }
        return null;
    }

See also how to transform a recursive method to an iterative one in a more generic way. Note that the example uses a stack, In your case a stack is not needed, since you only process one branch of the tree.

binary search tree (BST) find method in C#

1 Answers1