Iterative method to find height of binary tree

Binary tree is a data structure. Each node of a binary tree contains 0, 1, or 2 nodes. Therefore, a binary tree can contain multiple levels.

Here, we need to write iteration code using a loop to find the height of the binary tree. The total number of levels of a binary tree represents the height of the binary tree. Alternatively, we can say that the maximum depth of a binary tree from the root node is the height of the binary tree.

Problem Statement - We are given a binary tree. We need to use an iterative method to find the height of a given binary tree.

method 1

As we said above, the height of a binary tree is equal to the total number of levels of the binary tree. We will use a queue data structure to iterate through each node of each level and find the maximum depth of the tree.

algorithm

Step 1 - Define the "treeNode" class and add the "val" integer variable. Also, define "left" and "right" pointers in the class.

Step 2- Define the createNode() function to create a new node for the tree. It creates a new treeNode, initializes "val" with the parameter value, and initializes the left and right pointers with null values. Finally return the newly created node.

Step 3 - The findHeight() function is used to find the height of the binary tree.

Step 4 - Define the "levelqueue" queue to store all nodes of the current level, the "treeHeight", "n_cnt" variables and the "temp" node.

Step 5− If the head node is Null, return 0.

Step 6- Push the head node to the "levelQueue".

Step 7- Use a "while" loop to iterate until the "levelQueue" becomes empty.

Step 8- Increase "treeHeight" by 1 and initialize "n_cnt" with the size of the queue, representing the total number of nodes at the current level.

Step 9- Iterate through all elements of the queue.

Step 9.1 - Pop the first element of the queue.

Step 9.2 − If the current node has a left child node, insert it into the queue.

Step 9.3 − If the current node has a right child node, insert it into the queue.

Step 9.4 - Remove the first node from the queue.

Step 10- Return the value of the "treeHeight" variable.

Example

#include <iostream>
#include <queue>

using namespace std;
class treeNode {
public:
    int val;
    treeNode *left;
    treeNode *right;
};
treeNode *createNode(int val) {
    //Create a new node
    treeNode *temp = new treeNode();
    temp->val = val;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int fidHeight(treeNode *head) {
    queue<treeNode *> levelQueue;
    int treeHeight = 0; // To store the tree height of the current binary tree
    int n_cnt = 0;      // To store the total number of current level nodes.
    treeNode *temp;     // Pointer to store the address of a node in the current level.
    // For empty binary tree
    if (head == NULL) {
        return 0;
    }
    // Add root node to queue
    levelQueue.push(head);
    // Traverse level of binary tree
    while (!levelQueue.empty()) {
        // For each level increment, the treeHeight of the three
        treeHeight++;
        n_cnt = levelQueue.size();
        // Add child nodes of all nodes at the current level
        while (n_cnt--) {
            temp = levelQueue.front();
            // Insert the left child node of the current node
            if (temp->left != NULL) {
                levelQueue.push(temp->left);
            }
            // Insert the right child node of the current node
            if (temp->right != NULL) {
                levelQueue.push(temp->right);
            }
            // remove the current node
            levelQueue.pop();
        }
    }
    return treeHeight;
}
int main() {
    treeNode *head = NULL;
    // Adding nodes to binary tree.
    head = createNode(45);
    head->right = createNode(32);
    head->right->left = createNode(48);
    head->left = createNode(90);
    head->left->left = createNode(5);
    head->left->left->left = createNode(50);
    cout << "The given binary tree's treeHeight is " << fidHeight(head) << ".";
    return 0;
}

Output

The given binary tree's treeHeight is 4.

Time complexity - O(N) traversing each node.

Space Complexity - O(N) Storing nodes in the queue.

Iterative methods are always faster than recursive methods when solving any problem. Here we use loops and queues to iteratively find the maximum depth or height of a binary tree. However, a programmer might try to code a recursive method to find the height of a binary tree.

The above is the detailed content of Iterative method to find height of binary tree. For more information, please follow other related articles on the PHP Chinese website!