The height of a binary tree is the length of the longest path from the root node to the deepest leaf node in the tree. It is also defined as the number of edges in the longest path from the root node to any leaf node in the tree. Generally height of the root node is considered as 0, height of it’s child nodes is 1 and so on.
But some other definitions consider the height of root node as 1, height of it’s child node as 2 and so on. We use this definition of binary tree height in the programming examples below.
Finding height of a binary tree Recursively
In order to write code to find height of a binary tree recursively, we need to think of the main problem in terms of similar smaller problems. For a given binary tree root node, let’s say we have the height of it’s left subtree as left_height and right subtree and right_height. Now the height of root node is equal to the maximum of left or right subtree height plus one (for the link between child subtree and root node).
We have the recursive equation as follows:
height(root) = max(height(root->left), height(root->right)) + 1
Below is the full code which finds maximum height of a binary tree using recursion.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def height_of_binary_tree(node):
# If the node is empty (or tree is empty), return 0
if node is None:
return 0
else:
# Calculate the height of the left subtree
left_height = height_of_binary_tree(node.left)
# Calculate the height of the right subtree
right_height = height_of_binary_tree(node.right)
# Return the maximum height of left or right subtree,
# plus 1 for the current node
return max(left_height, right_height) + 1
# Create a sample binary tree for testing
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Let's now test the function which returns height of binary tree
if __name__ == "__main__":
tree_root = create_binary_tree()
height = height_of_binary_tree(tree_root)
print("Height of binary tree is :", height)
Finding height of a binary tree Iteratively
Height of a binary tree is similar to total number of levels/layers present in a binary tree. So we can perform level order traversal of the binary tree and count the number of levels/layers processed in total.
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def height_of_binary_tree(root):
# If the node is empty (or tree is empty), return 0
if root is None:
return 0
# Initialize height to 0
height = 0
# Create an queue with the starting level (root node)
queue = deque([root])
while queue:
# Get the size of the current level
level_size = len(queue)
# Process all nodes at the current level
for _ in range(level_size):
# Remove elements from left to right
current = queue.popleft()
# Add children of the current node to the deque
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
# Increment height after processing all nodes at the current level
height += 1
return height
# Create a sample binary tree for testing
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Let's test the function to find the height of the binary tree
if __name__ == "__main__":
tree_root = create_binary_tree()
height = height_of_binary_tree(tree_root)
print("Height of the binary tree is:", height)