Height of Tree

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

The most common type of tree is the binary tree. In this, each node has 2 children, i.e., Left and Right.

The node that doesn’t have any parents is known as the root node, and the node that doesn’t have any children nodes is known as the leaf node. There is one root node in a tree, but there can be numerous leaf nodes.

Takeaways

The maximum height of a tree in the data structure is the maximum distance between the root and the last leaf node.

What is the Height of a Tree in Data Structure?

The height of a tree (also known as depth) is the maximum distance between the root node of the tree and the leaf node of the tree. It can also be defined as the number of edges from the root node to the leaf node. The root node is at level 0. Therefore, if there is only one node, i.e., the root node, the height of the tree is 0.

The formula to determine the height of a n-ary tree with the help of the number of nodes (V) is:

If there are V nodes in an n-ary tree (a node can have at most n children), the maximum height of the tree is (V−1) and the minimum height is ceil(lognV).

How to Find the Height of a Tree in Data Structure?

As we know, the height of a tree is the longest or maximum distance between the leaf node and the root node. Therefore, we need to find the path between the root and all the leaf nodes and find the longest one of all.

Two Ways to Calculate the Height of a Tree

1. Recursive Way
2. Iterative Way

Let’s talk about the Recursive and Iterative ways by one-by-one in detail.

Recursive Way

Recursion involves dividing a large problem into smaller subproblems and returning the answer to their calls. We will work similarly to find the height of the tree. We will calculate the results of the subproblems and then return their results to the parent problem.

Algorithm

1. In order to calculate the height of the tree, we have to find the height of the left and right subtree recursively and then add 1 to them, i.e., the height between the topmost node and its children.
2. The recursion will run until the subtrees are NULL or the height of the tree is 1.
3. And finally, we will compare the heights of the left and right subtrees and return to the larger one.

Code

C++

// Recursive function to calculate the height of a given tree
int height(Node *root){
    // Base case: Empty tree has a height equals 0
    if (root == nullptr){
        return 0;
    }

    // Calling Left and Right node recursively
    return 1 + max(height(root->left), height(root->right));
}

Java

// Recursive function to calculate the height of a given tree
public static int height(Node root){
    // Base case: Empty tree has a height equals 0
    if (root == null) {
        return 0;
    }

    // Calling Left and Right node recursively
    return 1 + Math.max(height(root.left), height(root.right));
}

Python

# Recursive function to calculate the height of a given tree
def height(root):

    # Base case: Empty tree has a height equals 0
    if root is None:
        return 0
        
    # Calling Left and Right node recursively
    return 1 + max(height(root.left), height(root.right))

Complexity Analysis

• Time ComplexityThe above recursive solution has an O(n) time complexity, where n is the total number of nodes in the binary tree.
• Space ComplexityThe program needs O(h) of additional space for the call stack, where h is the tree’s height.

Iterative Way

In the iterative method, we find the height of the tree using the queue data structure. In this, we traverse the whole tree in a level-order traversal format where we maintain the nodes of each tree level in a queue data structure until all the levels are traversed and return the count of the number of levels.

Algorithm

1. Insert the root of a tree into a queue.
2. Traverse the tree in level order, inserting the child elements of all currently present nodes in the queue and removing those nodes.
3. Increment Count for each level in the queue.
4. Return the value of the counter when the queue becomes empty, i.e., when all the levels of the tree are traversed.

Code

C++

int height(Node *root){
    // Empty tree has a height equals 0
    if (root == nullptr){
        return 0;
    }

    // Create an empty queue and insert the root node
    list<Node *> queue;
    queue.push_back(root);

    Node *front = nullptr;
    int height = 0;

    // Run a loop until queue is empty
    while (!queue.empty()){
        // Calculate the total number of nodes at the current level
        int size = queue.size();

        while (size--){
            front = queue.front();
            queue.pop_front();

            if (front->left){
                queue.push_back(front->left);
            }

            if (front->right){
                queue.push_back(front->right);
            }
        }

        // Increment height by 1 for each level
        height++;
    }

    return height;
}

Java

public static int height(Node root){
        // Empty tree has a height equals 0
        if (root == null) {
            return 0;
        }
 
        // Create an empty queue and insert the root node
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
 
        Node front = null;
        int height = 0;
 
        // Run a loop until queue is empty
        while (!queue.isEmpty()){
            // Calculate the total number of nodes at the current level
            int size = queue.size();

            while (size-- > 0){
                front = queue.poll();
 
                if (front.left != null) {
                    queue.add(front.left);
                }
 
                if (front.right != null) {
                    queue.add(front.right);
                }
            }
 
            // Increment height by 1 for each level
            height++;
        }
 
        return height;
    }

Python

def height(root):

    # Empty tree has a height equals 0
    if root is None:
        return 0

    # Create an empty queue and insert the root node
    queue = deque()  # import deque
    queue.append(root)

    height = 0

    # Run a loop until queue is empty
    while queue:

        # Calculate the total number of nodes at the current level
        size = len(queue)

        while size > 0:
            front = queue.popleft()

            if front.left:
                queue.append(front.left)

            if front.right:
                queue.append(front.right)

            size = size - 1

        # Increment height by 1 for each level
        height = height + 1

    return height

Complexity Analysis

• Time ComplexityThe time complexity of the above iterative solution is O(n), where n is the total number of nodes in the binary tree.
• Space ComplexityThe auxiliary space required by the program is O(n) for the queue data structure.

Ready to transform your coding skills? Our Java DSA course will equip you with the tools to solve real-world programming challenges.

Conclusion

Let’s summarize the article by what we have discussed so far.

• A tree is a hierarchical data structure with parent and child nodes.
• There is a single root node and a number of leaf nodes.
• If there are V nodes in an n-ary tree (a node can have at most n children), the maximum height of the tree is (V−1), and the minimum height is ceil(lognV)ceil(lognV).
• The height of a tree can be calculated using recursive and iterative methods.