How to Find Height of Tree in Data Structures

To find the height of a tree, use a recursive approach that calculates the height of each subtree and returns the maximum height plus one. The height is the number of edges on the longest path from the root to a leaf node.

Syntax

The typical syntax for finding the height of a tree uses a recursive function that takes a node as input and returns an integer height.

• if node is null: return 0 (base case)
• left_height = height(node.left) - find height of left subtree
• right_height = height(node.right) - find height of right subtree
• return max(left_height, right_height) + 1 - height is max subtree height plus one for current node

python

def height(node):
    if node is None:
        return 0
    left_height = height(node.left)
    right_height = height(node.right)
    return max(left_height, right_height) + 1

Example

This example demonstrates how to define a simple binary tree and find its height using the recursive function.

python

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def height(node):
    if node is None:
        return 0
    left_height = height(node.left)
    right_height = height(node.right)
    return max(left_height, right_height) + 1

# Create tree:
#      1
#     / \
#    2   3
#   / 
#  4
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print(height(root))

Output

3

Common Pitfalls

Common mistakes when finding tree height include:

• Not handling the base case where the node is None, which causes errors or infinite recursion.
• Confusing height with the number of nodes; height counts edges, so the height of a single node tree is 0.
• Using iterative methods without proper stack or queue management, which can complicate the solution unnecessarily.

python

def wrong_height(node):
    # Missing base case
    left_height = wrong_height(node.left)
    right_height = wrong_height(node.right)
    return max(left_height, right_height) + 1

# Correct way includes base case:

def correct_height(node):
    if node is None:
        return 0
    left_height = correct_height(node.left)
    right_height = correct_height(node.right)
    return max(left_height, right_height) + 1

Quick Reference

Tips for finding tree height:

• Always check for None nodes as base case.
• Use recursion to explore left and right subtrees.
• Return the maximum height of subtrees plus one.
• Height counts edges from root to deepest leaf.

Key Takeaways

Use recursion with a base case to find the height of a tree.

Height is the longest path from root to leaf counted in edges.

Always return max height of left and right subtrees plus one.

Handle empty nodes properly to avoid errors.

Height of a single node tree is 0, not one.