หาค่าน้อยที่สุดใน Binary Search Tree (BST) ใน C++

ใน BST โหนดด้านซ้ายมีค่าน้อยกว่าโหนดปัจจุบันเสมอ ดังนั้นค่าน้อยที่สุดอยู่ที่โหนดซ้ายสุด

อัลกอริทึม

1. เริ่มจาก Root
2. วนลูปไปทางซ้ายจนกว่า Left จะเป็น NULL
3. คืนค่าของโหนดนั้น

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

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

Node* bst = NULL;

Node* getNode() {
    return new Node();
}

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 items[] = {3, 2, 1, 6, 5, 8};
    int n = sizeof(items) / sizeof(items[0]);

    for (int i = 0; i < n; i++)
        insert(&bst, items[i]);

    cout << "Minimum element is: " << minElement();
    return 0;
}

ผลลัพธ์

Minimum element is: 1

ความซับซ้อน

เวลา: O(h) โดย h = ความสูงของต้นไม้ (O(log n) สำหรับ BST สมดุล, O(n) สำหรับ BST เบี้ยว)

พื้นที่: O(1) (Iterative)

เวอร์ชัน Recursive

int minElementRecursive(Node* root) {
    if (root->left == NULL) return root->val;
    return minElementRecursive(root->left);
}