🎓 A1Learner
🔍
0 of 47 lessons completed

Practice: Tree Problems

Practice with tree problems is work on problems where each value branches into smaller child problems. It turns tree walks from earlier lessons into speed and accuracy under time pressure.

Spot a tree problem

The input branches from a root into children. The question asks about a path, a depth, or a value inside a subtree.

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

root = Node(10, Node(5), Node(15))
print("Root:", root.value)
print("Left:", root.left.value)
print("Right:", root.right.value)

The recursive walk template

A recursive walk visits a node, then walks its left child, then its right child. The same small step handles every subtree.

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

def walk(node, out):
    if node is None:
        return
    out.append(str(node.value))
    walk(node.left, out)
    walk(node.right, out)

root = Node(10, Node(5, Node(3)), Node(15))
parts = []
walk(root, parts)
print(" ".join(parts))

Worked problem: find the depth

The depth of a node is one plus the deeper of its two child depths. An empty child has depth zero, which stops the walk.

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

def depth(node):
    if node is None:
        return 0
    return 1 + max(depth(node.left), depth(node.right))

root = Node(1, Node(2, Node(4)), Node(3))
print("Depth:", depth(root))

Example

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

def search(node, target):
    if node is None:
        return False
    if node.value == target:
        return True
    return search(node.left, target) or search(node.right, target)

root = Node(8, Node(3), Node(10))
print("Found 10:", search(root, 10))
print("Found 5:", search(root, 5))

Key points

  • A tree is a branching structure with one root and child nodes below it.
  • Use a recursive walk to visit a node and then its children.
  • Use a level-by-level walk when the question asks about depth or the nearest value.
  • A subtree is the node plus everything below it, so many tree answers combine child answers.

The search checks the node first, then its children. A match anywhere below the root returns true. An empty child returns false, which ends that branch.

Note

a tree walk must handle an empty child, or the walk will fail.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A problem asks for the number of leaf nodes in a tree. Which approach fits best?