C++의 이진 검색 트리에서 최소값을 갖는 노드 찾기

하나의 이진 검색 트리가 있다고 가정합니다. 이진 탐색 트리에서 최소 요소를 찾아야 합니다. 따라서 BST가 아래와 같으면 -

최소 요소는 1입니다.

왼쪽 하위 트리는 항상 더 작은 요소를 보유한다는 것을 알고 있습니다. 따라서 왼쪽 하위 트리를 계속해서 왼쪽이 null이 될 때까지 탐색하면 가장 작은 요소를 찾을 수 있습니다.

예시

#include<iostream>
using namespace std;
class node{
   public:
      node *left;
      int val;
      node *right;
};
node *bst = NULL;
node *getNode(){
   node *newNode;
   newNode = new node;
   return newNode;
}
void insert(node **root, int key){
   node *newNode;
   newNode = getNode();
   newNode->val = key; newNode->left = NULL; newNode->right = NULL;
   if(*root == NULL){
      *root = newNode;
      return;
   } else {
      if(key < (*root)->val)
      insert(&((*root)->left), key);
   else
      insert(&((*root)->right), key);
   }
}
int minElement(){
   node* current = bst;
   while (current->left != NULL) {
      current = current->left;
   }
   return(current->val);
}
main(){
   int item[] = {3, 2, 1, 6, 5, 8};
   int n = sizeof(item)/sizeof(item[0]);
   int i;
   for(i = 0; i<8; i++){
      insert(&bst, item[i]);
   }
   cout << "Minimum element is: " << minElement();
}

출력

Minimum element is: 1