Find the Maximum Depth or Height of a Tree using Level Order Traversal

Do Level Order Traversal, while adding Nodes at each level to Queue, we have to add NULL Node so that whenever it is encountered, we can increment the value of variable and that level get counted.

"Level Order Traversal"을 사용하여 트리의 최대 깊이 또는 높이를 찾는 문제는 주어진 트리의 레벨 순서로 노드를 탐색하여 트리의 최대 깊이 또는 높이를 찾는 문제입니다.

일반적으로 이 문제를 해결하기 위해 큐(Queue) 자료구조를 사용하여 너비 우선 탐색(Breadth-First Search, BFS)을 수행합니다. BFS를 사용하면 트리의 각 레벨을 하나씩 순회하며 레벨의 노드 수를 세고, 이 중 가장 많은 노드를 포함한 레벨의 노드 수를 트리의 최대 깊이 또는 높이로 간주합니다.

이러한 문제는 이진 트리(Binary Tree)나 일반적인 트리(Tree) 구조에서 사용됩니다. 주어진 트리를 레벨 순서로 탐색하고 최대 깊이 또는 높이를 계산하는 알고리즘을 구현하는 것이 이 문제의 목적입니다.

 

이 코드는 이진 트리의 높이(또는 깊이)를 계산하는 C++ 프로그램입니다. 이 코드에서는 너비 우선 탐색(Breadth-First Search, BFS)을 사용하여 트리의 높이를 찾습니다.

코드의 주요 구성 요소와 동작은 다음과 같습니다:

1. struct Node 구조체: 트리의 노드를 나타내는 구조체입니다. 각 노드는 키(key) 값을 가지며, 왼쪽 자식 노드(left)와 오른쪽 자식 노드(right)의 포인터를 가집니다.
2. newNode 함수: 새로운 노드를 생성하고 초기화하는 함수입니다. 주어진 key 값을 가지는 새로운 노드를 동적으로 생성하고 반환합니다.
3. height 함수: 이 함수는 트리의 높이를 계산하는 핵심 함수입니다. BFS 방식으로 트리를 순회하여 높이를 계산합니다.
   • depth 변수: 트리의 높이를 저장하는 변수로 초기값은 0입니다.
   • queue<Node*> q: BFS를 위한 큐입니다. 노드 포인터를 저장합니다.
   • 루트 노드를 큐에 추가하고 NULL을 추가하여 첫 번째 레벨을 표시합니다.
   • 큐가 비어 있지 않을 때까지 다음 작업을 반복합니다:
     • 큐에서 노드를 하나 꺼내고(temp), NULL인 경우 레벨이 증가합니다.
     • temp가 NULL이 아닌 경우, 왼쪽 자식 노드와 오른쪽 자식 노드가 있는 경우 큐에 추가합니다.
     • 큐에 아직 처리해야 할 노드가 남아 있으면 다음 레벨을 표시하기 위해 NULL을 큐에 추가합니다.
   • 이렇게 반복하여 트리의 모든 레벨을 순회하면서 높이를 계산합니다.
4. main 함수: 프로그램의 진입점으로, 이진 트리를 생성하고 height 함수를 호출하여 트리의 높이를 계산하고 출력합니다.

struct Node {
    int key;
    struct Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
/*Function to find the height(depth) of the tree*/
int height(struct Node* root)
{
 
    // Initialising a variable to count the
    // height of tree
    int depth = 0;
 
    queue<Node*> q;
 
    // Pushing first level element along with NULL
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
 
        // When NULL encountered, increment the value
        if (temp == NULL) {
            depth++;
        }
 
        // If NULL not encountered, keep moving
        if (temp != NULL) {
            if (temp->left) {
                q.push(temp->left);
            }
            if (temp->right) {
                q.push(temp->right);
            }
        }
 
        // If queue still have elements left,
        // push NULL again to the queue.
        else if (!q.empty()) {
            q.push(NULL);
        }
    }
    return depth;
}

queue에서 해당 node의 자식들이 있을 경우 추가한 후, null 값을 추가함으로써 queue를 pop할 때 null값을 보고 depth를 증가시키는 방법이다.