Tìm nút giá trị nhỏ nhất trong cây nhị phân tìm kiếm (BST) trong C++

Trong BST, cây con trái luôn chứa giá trị nhỏ hơn. Để tìm phần tử nhỏ nhất: bắt đầu từ gốc, liên tục đi sang trái cho đến khi không còn con trái.

Ví dụ

#include <iostream>
using namespace std;

class node {
public:
    node *left;
    int val;
    node *right;
};

node *bst = NULL;
node *getNode() {
    node *newNode = new node;
    return newNode;
}

void insert(node **root, int key) {
    node *newNode = getNode();
    newNode->val = key;
    newNode->left = newNode->right = NULL;
    if (*root == NULL) {
        *root = newNode;
        return;
    }
    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;
}

int main() {
    int item[] = {3, 2, 1, 6, 5, 8};
    int n = sizeof(item) / sizeof(item[0]);
    for (int i = 0; i < n; i++)
        insert(&bst, item[i]);
    cout << "Minimum element is: " << minElement();
}

Kết quả

Minimum element is: 1