Xây BST từ preorder traversal (Phương pháp 2 - Stack) trong C++

Cho preorder traversal của BST. Xây dựng cây. Ví dụ: [10, 5, 1, 7, 40, 50].

Thuật toán dùng Stack

1. Tạo stack rỗng
2. Phần tử đầu = gốc, push vào stack
3. Với mỗi phần tử tiếp theo:
   • Pop stack khi không rỗng và giá trị > stack.top() → nút pop cuối = cha, phần tử hiện tại = con phải
   • Nếu không pop được: stack.top() = cha, phần tử hiện tại = con trái
   • Push nút mới vào stack

Chương trình C++

#include <iostream> 
#include <stack> 
using namespace std; 

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

node* getNode(int data) {
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

node* constructTree(int pre[], int size) {
    stack<node*> stk;
    node* root = getNode(pre[0]);
    stk.push(root);
    
    for (int i = 1; i < size; ++i) {
        node* temp = NULL;
        while (!stk.empty() && pre[i] > stk.top()->data) {
            temp = stk.top();
            stk.pop();
        }
        if (temp != NULL) {
            temp->right = getNode(pre[i]);
            stk.push(temp->right);
        } else {
            node* peek_node = stk.top();
            peek_node->left = getNode(pre[i]);
            stk.push(peek_node->left);
        }
    }
    return root;
}

void inord(node* node) {
    if (node == NULL) return;
    inord(node->left);
    cout << node->data << " ";
    inord(node->right);
}

int main() {
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof(pre) / sizeof(pre[0]);
    node *root = constructTree(pre, size);
    cout << "Inorder traversal: ";
    inord(root);
}

Kết quả

Inorder traversal: 1 5 7 10 40 50

Độ phức tạp

• Thời gian: O(n) - mỗi nút push/pop tối đa 1 lần
• Không gian: O(n) cho stack