a Develop a recursive algorithm to find the smallest node in

(a) Develop a recursive algorithm to find the smallest node in a binary search tree. (b) Develop a nonrecursive algorithm to find the smallest node in a binary search tree. Write both algorithms in psuedocode.

Solution

Hi, please find my code.

Smallest element in Binary Search Tree is left most node of tree.

PSUDO CODE :

1. Recursive

   Node smallestNode(Node root){
       // base case. tree is empty
       if(root == null)
           return null;

       // we reach at left most node of tree
       if(root.left == null)
           return root;

       else
           return smallestNode(root.left); // going left
   }

2. Iterative

   Node smallestNode(Node root){
       // base case. tree is empty
       if(root == null)
           return null;
       // go left till you hit left most node
       while(root.left != null){
           root = root.left;
       }

       return root;

   }