หาโหนดขวาถัดไปของคีย์ใน Binary Tree ด้วย C++

ภาพรวมปัญหา

ได้รับ Binary Tree และคีย์ (key) ต้องหาโหนดที่อยู่ข้างขวาถัดไปในระดับเดียวกัน (Level Order)

ตัวอย่าง

อินพุต

key = 4

เอาต์พุต

5

คำอธิบาย

โหนดข้างขวาของ 4 ในระดับเดียวกันคือ 5

วิธีแก้ปัญหา

ใช้ Level Order Traversal (BFS) พร้อมเก็บระดับของแต่ละโหนด

1. Enqueue root พร้อม level = 0
2. Dequeue โหนด ถ้า key ตรงกัน → ตรวจสอบ front ของ queue ว่าอยู่ level เดียวกันไหม
3. ถ้าใช่ → คืนค่าโหนดนั้น ถ้าไม่ → NULL
4. Enqueue ลูกซ้ายและขวา พร้อม level+1

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

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

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

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

Node* findNextRightNodeBT(Node *root, int k) {
    if (root == NULL) return NULL;
    
    queue<Node*> q;
    queue<int> levelQ;
    
    q.push(root);
    levelQ.push(0);
    
    while (!q.empty()) {
        Node *node = q.front(); q.pop();
        int level = levelQ.front(); levelQ.pop();
        
        if (node->key == k) {
            if (levelQ.empty() || levelQ.front() != level)
                return NULL;
            return q.front();
        }
        
        if (node->left) {
            q.push(node->left);
            levelQ.push(level + 1);
        }
        if (node->right) {
            q.push(node->right);
            levelQ.push(level + 1);
        }
    }
    return NULL;
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    
    int key = 4;
    cout << "The next right node of the node " << key << " is ";
    Node *nextNode = findNextRightNodeBT(root, key);
    if (nextNode != NULL)
        cout << nextNode->key;
    else
        cout << "not available";
    return 0;
}

เอาต์พุต

The next right node of the node 4 is 5

สรุป

BFS/Level Order Traversal เป็นวิธีธรรมชาติสำหรับปัญหา "โหนดข้างขวาในระดับเดียวกัน" Complexity O(N)