Tree Traversals 15 XP Easy

Ctrl+Enter Run Ctrl+S Save

Tree Traversals are the ways to visit every node in a binary tree. There are three main orders — and they're all just 3 lines of code! 🌳

💡 Think of it like this: Imagine you're in a building checking every room. Do you check the current floor first, or go straight upstairs? The three traversals differ in WHEN you visit the current node:

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

Level-Order Traversal (BFS): Visit level by level using a queue.

from collections import deque

def levelOrder(root):
    if not root: return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result
# Result: [[1], [2, 3], [4, 5]]

Remember: In/Pre/Post refers to when you visit the ROOT. In-order = root in the middle. Pre-order = root first. Post-order = root last.

📋 Instructions

Implement all three traversals and print the results for the tree above.

Inorder: recurse left, visit root, recurse right. Preorder: visit root, recurse left, recurse right. Postorder: recurse left, recurse right, visit root.

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

#       1
#      / \
#     2   3
#    / \
#   4   5

def inorder(node):       # Left → ROOT → Right
    if not node: return
    inorder(node.left)   #   Result: 4, 2, 5, 1, 3
    print(node.val)      #   (Gives SORTED order in BST!)
    inorder(node.right)

def preorder(node):      # ROOT → Left → Right
    if not node: return
    print(node.val)      #   Result: 1, 2, 4, 5, 3
    preorder(node.left)  #   (Used to COPY a tree)
    preorder(node.right)

def postorder(node):     # Left → Right → ROOT
    if not node: return
    postorder(node.left)   # Result: 4, 5, 2, 3, 1
    postorder(node.right)  # (Used to DELETE a tree)
    print(node.val)

🧪 Test Cases

Input

inorder(root)

Expected

[4, 2, 5, 1, 3]

Test case 1

Input

preorder(root)

Expected

[1, 2, 4, 5, 3]

Test case 2

Input

postorder(root)

Expected

[4, 5, 2, 3, 1]

Test case 3

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›