Height of Binary Tree in DSA Python - Build from Scratch

Height of Binary Tree

📖 Scenario: You are working on a program that helps analyze family trees. Each person can have children, forming a tree structure. You want to find out how many generations are in the family tree, which is the height of the tree.

🎯 Goal: Build a program that creates a simple binary tree, then calculates and prints its height (the number of levels from the root to the deepest leaf).

📋 What You'll Learn

Create a binary tree node class called Node with data, left, and right attributes

Manually build a binary tree with 3 levels

Write a function called height that calculates the height of the binary tree

Print the height of the tree

💡 Why This Matters

🌍 Real World

Binary trees are used in many areas like organizing family trees, file systems, and decision processes.

💼 Career

Understanding tree height is important for jobs involving data structures, algorithms, and software engineering.

1

Create the Node class and build the binary tree

Create a class called Node with an __init__ method that takes data and sets left and right to None. Then create the root node with data 1, its left child with data 2, and its right child with data 3. Also add left and right children to node 2 with data 4 and 5 respectively.

DSA Python

# Define the Node class and create the binary tree nodes
# Your code here

Hint

Define the Node class first. Then create nodes and link them using left and right attributes.

2

Create a function to calculate the height of the tree

Define a function called height that takes a node as input. If the node is None, return 0. Otherwise, recursively find the height of the left subtree and the right subtree, then return 1 + max(left_height, right_height).

DSA Python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Define the height function below
# Your code here

Hint

Use recursion to find the height of left and right children, then add 1 for the current node.

3

Calculate the height of the tree

Call the height function with the root node and store the result in a variable called tree_height.

DSA Python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

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

# Calculate the height of the tree and store it in tree_height
# Your code here

Hint

Simply call height(root) and save the result in tree_height.

4

Print the height of the binary tree

Print the value of tree_height.

DSA Python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

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

tree_height = height(root)

# Print the height of the tree
# Your code here

Hint

Use print(tree_height) to show the height.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. 2

B. 0

C. Undefined

D. 1

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of nodes on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Height of single node tree = 1 [OK]

Hint: Height counts nodes on longest root-to-leaf path [OK]

Common Mistakes:

• Thinking height is 0 for single node
• Confusing height with number of edges
• Assuming height is undefined for single node

2. Which of the following is the correct Python function header to calculate the height of a binary tree node named root?

easy

A. def height(root, node):

B. def height(root):

C. def height():

D. def height(tree_root):

Solution

1. Step 1: Identify function parameter

   The function needs one parameter representing the root node of the tree.

2. Step 2: Match parameter name and count

   def height(root): uses one parameter named root, which matches the question context.

3. Final Answer:

   def height(root): -> Option B

4. Quick Check:

   One parameter named root is correct [OK]

Hint: Function needs one parameter: the root node [OK]

Common Mistakes:

• Adding extra parameters unnecessarily
• No parameters in function
• Using unrelated parameter names

3. What will be the output of the following code snippet?

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

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

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
print(height(root))

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace tree structure

   The tree has root 10, with left child 20 and right child 30. Node 20 has left child 40. The longest path is 10 -> 20 -> 40.

2. Step 2: Calculate height recursively

   Height is max height of left and right subtree plus 1. Left subtree height is 2 (20 -> 40), right subtree height is 1 (30). So total height = max(2,1)+1 = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path length = 3 [OK]

Hint: Count nodes on longest root-to-leaf path [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring one subtree height
• Returning wrong base case value

4. Find the error in this height calculation function and choose the correct fix:

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

medium

A. Add else before recursive calls

B. Change max to min in return statement

C. Change base case return from -1 to 0

D. Remove +1 from return statement

Solution

1. Step 1: Understand base case meaning

   Height of empty tree (None) should be 0, not -1, to count nodes properly.

2. Step 2: Fix base case return value

   Changing return -1 to return 0 fixes height calculation to count nodes correctly.

3. Final Answer:

   Change base case return from -1 to 0 -> Option C

4. Quick Check:

   Base case height = 0 for empty tree [OK]

Hint: Base case for empty node should return 0 [OK]

Common Mistakes:

• Returning -1 causes height off by one
• Using min instead of max
• Forgetting to add 1 after recursion

5. Given a binary tree where each node has a value, write a function to find the height of the tree but only counting nodes with even values. What will be the height of this tree?

    2
   / \
  3   4
     / \
    6   7
   /
  8

hard

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Identify even-valued nodes in tree

   Nodes with even values: 2 (root), 4, 6, 8. Nodes 3 and 7 are odd and ignored.

2. Step 2: Calculate height counting only even nodes

   Longest path with even nodes is 2 -> 4 -> 6 -> 8, but since 4 has children 6 and 7, and 7 is odd, it is ignored. The path length counting only even nodes is 4 nodes, but the height counts edges between nodes, so height is 3.

3. Step 3: Clarify height definition for this problem

   Height counts number of edges on longest path with even values only. The path is 2 -> 4 -> 6 -> 8, which has 3 edges, so height is 3.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   Longest even-valued path edge count = 3 [OK]

Hint: Count only even nodes on longest root-to-leaf path, height = edges count [OK]

Common Mistakes:

• Counting odd nodes by mistake
• Confusing edges with nodes
• Ignoring subtree with even nodes