พิมพ์โหนดร่วมของสอง Binary Search Trees ใน C++

โจทย์

ให้สอง Binary Search Trees (BST) ต้องการหาโหนดที่มีค่าเหมือนกันในทั้งสองต้นไม้

วิธีแก้ปัญหา (Iterative Inorder + 2 Stacks)

ทำ Inorder Traversal ทั้งสองต้นพร้อมกันโดยใช้ Stack 2 ตัว:

1. ดันซ้ายสุดทั้งสองต้น push เข้า stack
2. เปรียบเทียบ top ของทั้งสอง stack:
   • เท่ากัน → พิมพ์ค่า, pop ทั้งคู่, ไปขวาทั้งคู่
   • tree1 < tree2 → pop tree1, ไปขวา tree1, tree2 = NULL
   • tree1 > tree2 → pop tree2, ไปขวา tree2, tree1 = NULL
3. ทำซ้ำจน stack ว่าง

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

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

struct Node {
    int key;
    struct Node *left, *right;
};

Node* newNode(int ele) {
    Node* temp = new Node;
    temp->key = ele;
    temp->left = temp->right = NULL;
    return temp;
}

void printCommon(Node* tree1, Node* tree2) {
    stack<Node*> s1, s2;
    while (1) {
        if (tree1) { s1.push(tree1); tree1 = tree1->left; }
        else if (tree2) { s2.push(tree2); tree2 = tree2->left; }
        else if (!s1.empty() && !s2.empty()) {
            tree1 = s1.top(); tree2 = s2.top();
            if (tree1->key == tree2->key) {
                cout << tree1->key << " ";
                s1.pop(); s2.pop();
                tree1 = tree1->right; tree2 = tree2->right;
            } else if (tree1->key < tree2->key) {
                s1.pop(); tree1 = tree1->right; tree2 = NULL;
            } else {
                s2.pop(); tree2 = tree2->right; tree1 = NULL;
            }
        } else break;
    }
}

void inorderTraversal(struct Node* root) {
    if (root) { inorderTraversal(root->left); cout << root->key << " "; inorderTraversal(root->right); }
}

struct Node* insertNode(struct Node* node, int key) {
    if (node == NULL) return newNode(key);
    if (key < node->key) node->left = insertNode(node->left, key);
    else if (key > node->key) node->right = insertNode(node->right, key);
    return node;
}

int main() {
    Node* tree1 = NULL;
    tree1 = insertNode(tree1, 45);
    tree1 = insertNode(tree1, 87);
    tree1 = insertNode(tree1, 12);
    tree1 = insertNode(tree1, 54);
    tree1 = insertNode(tree1, 89);
    tree1 = insertNode(tree1, 19);
    tree1 = insertNode(tree1, 72);
    cout << "Binary Tree 1: "; inorderTraversal(tree1); cout << endl;
    Node* tree2 = NULL;
    tree2 = insertNode(tree2, 72);
    tree2 = insertNode(tree2, 23);
    tree2 = insertNode(tree2, 13);
    tree2 = insertNode(tree2, 1);
    tree2 = insertNode(tree2, 19);
    cout << "Binary Tree 2: "; inorderTraversal(tree2); cout << endl;
    cout << "Common Nodes: "; printCommon(tree1, tree2);
    return 0;
}

ผลลัพธ์

Binary Tree 1: 12 19 45 54 72 87 89
Binary Tree 2: 1 13 19 23 72
Common Nodes: 19 72