เขียนโปรแกรมหาความสูงสูงสุด (Height/Depth) ของต้นไม้ใน C++

โจทย์

ได้รับ Binary Tree ต้องการเขียนโปรแกรมหาความสูงสูงสุด (Maximum Depth/Height) ของต้นไม้

นิยาม

ความสูงของต้นไม้ (Height) = จำนวนโหนดบนเส้นทางยาวที่สุดจากราก (root) ไปยังใบ (leaf) หรือจำนวน edges บนเส้นทางนั้น (ขึ้นกับนิยาม)

ตัวอย่าง

ความสูงของต้นไม้ = 3

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

ความสูงของโหนด = max(ความสูงซ้าย, ความสูงขวา) + 1

height(node) = max(height(node->left), height(node->right)) + 1
Base case: height(nullptr) = 0

ตัวอย่างการคำนวณ

height(3) = max(height(5), height(7)) + 1
height(5) = max(height(1), height(9)) + 1 = max(1, 1) + 1 = 2
height(7) = 1 (ไม่มีลูก)
height(3) = max(2, 1) + 1 = 3

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

#include <iostream>
using namespace std;

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

int height(Node* node) {
    if (node == nullptr) return 0;
    
    int lDepth = height(node->left);
    int rDepth = height(node->right);
    
    return max(lDepth, rDepth) + 1;
}

Node* insertNode(int data) {
    Node* node = new Node();
    node->data = data;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

int main() {
    Node* root = insertNode(4);
    root->left = insertNode(5);
    root->right = insertNode(0);
    root->left->left = insertNode(1);
    root->left->right = insertNode(9);
    //       4
    //      / \
    //     5   0
    //    / \
    //   1   9
    
    cout << "The height of the given binary tree is " << height(root);
    return 0;
}

ผลลัพธ์

The height of the given binary tree is 3

Iterative Version (BFS - Level Order)

int heightIterative(Node* root) {
    if (!root) return 0;
    
    queue<Node*> q;
    q.push(root);
    int h = 0;
    
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            Node* curr = q.front(); q.pop();
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
        h++;
    }
    return h;
}

Iterative Version (DFS with Stack)

int heightDFS(Node* root) {
    if (!root) return 0;
    
    stack<pair<Node*, int>> st;
    st.push({root, 1});
    int maxH = 0;
    
    while (!st.empty()) {
        auto [node, depth] = st.top(); st.pop();
        maxH = max(maxH, depth);
        if (node->left) st.push({node->left, depth + 1});
        if (node->right) st.push({node->right, depth + 1});
    }
    return maxH;
}

Complexity

• Time: O(N) - เข้าชมทุกโหนดครั้งเดียว
• Space (Recursive): O(H) - recursion stack
• Space (Iterative BFS): O(W) - W = ความกว้างสูงสุด (max width)
• Space (Iterative DFS): O(H) - explicit stack

สรุป

การหาความสูงต้นไม้เป็นปัญหาพื้นฐานที่ใช้ recursion ได้อย่างเป็นธรรมชาติ Recursive version เขียนง่ายที่สุด Iterative BFS ใช้เมื่อ tree กว้างแต่นึกสั้น Iterative DFS ใช้เมื่อ tree ลึกมากและต้องการหลีกเลี่ยง recursion limit