Binary Tree Basics 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

A Binary Tree is a hierarchical data structure where each node has at most two children: left and right. Trees appear in about 30% of coding interviews! 🌳

💡 Think of it like this: A binary tree is like a family tree, but each person can have at most 2 children. The person at the very top is the root, and people at the bottom with no kids are called leaves.

💭 Now it's your turn! Using the approach above, implement your solution in the editor. You've got this! 💪

Key Tree Vocabulary:

🌱 Root — The topmost node (node 1 above). Every tree has exactly one.
🍃 Leaf — A node with NO children (nodes 3, 4, 5 above)
📏 Height/Depth — How many levels from root to the deepest leaf
👨‍👧‍👦 Parent/Child — Node 2 is parent of 4 and 5
🌿 Subtree — Any node plus ALL its descendants

The Big Secret: Almost every tree problem uses recursion. Why? Because the left subtree and right subtree are themselves trees! So you solve the same problem on smaller pieces.

# Counting nodes — the recursive pattern:
def count(node):
    if node is None:       # Base case: empty tree has 0 nodes
        return 0
    return 1 + count(node.left) + count(node.right)
    #      ^me   ^left subtree    ^right subtree

This pattern of "do something with current node + recurse left + recurse right" is used in almost every tree problem. Master it! 💪

📋 Instructions

Create a binary tree and count the total number of nodes using recursion. Build the tree shown above (1 as root, 2 and 3 as children, 4 and 5 as children of 2). Count all nodes.

A recursive count: if node is None, return 0. Otherwise return 1 + count(left) + count(right). This visits every node exactly once: O(n).

⚠️ Try solving it yourself first — you'll learn more!

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

#       1        ← root
#      / \
#     2   3      ← children of 1
#    / \
#   4   5        ← children of 2 (3, 4, 5 are leaves)

🧪 Test Cases

Input

count_nodes(root)

Expected

5

Test case 1

Input

count_nodes(root.left)

Expected

3

Test case 2

Input

count_nodes(None)

Expected

0

Edge case — null/empty input

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›