Solving Search and Aggregation Problems with Binary-Tree Traversal

Choose when to process a node

Consider this tree:

        7
      /   \
     3     12
    / \   /  \
  -4   5 5    9

Depth-first traversal does not specify a unique visit order. It specifies that you explore a subtree before moving on to another; when you process its root determines the order:

Read the short traversal descriptions below. Their examples use C++, but focus on where the operation on the current node sits relative to the two child calls.

An ordinary binary tree does not promise that its inorder values are sorted. That would require an additional ordering invariant. For this lesson, neither the target search nor the sum can safely skip a subtree on the basis of its values.

Level order uses the queue you already know. For the two problems here, recursive depth-first traversal is especially convenient: the call stack remembers which parent to return to after finishing a child. Preorder suits a search that checks the current node immediately. Postorder suits an aggregation whose answer depends on completed child subtrees.

Aggregation: give each call a precise contract

Suppose sum_values(node) means the sum of all values in the subtree rooted at node. That contract applies equally to the root, either child, and a leaf. An empty subtree has sum zero; for a nonempty subtree, combine its root value with the sums returned by its children:

For the tree above, the subtree rooted at 3 contributes $3+(-4)+5=4$; the subtree rooted at 12 contributes $12+5+9=26$. The root’s result is therefore $7+4+26=37$. Notice that the right subtree contains another 5: aggregation counts nodes, not distinct values.

The following excerpt makes the return path visible. Watch how a completed child call supplies a result to its parent rather than modifying a global total.

There is no separate postorder-printing operation in this sum. The combination happens after the child calls return, which is the postorder idea applied to a calculation.

Search: return early, but only on evidence

Now define find_value(node, target) to return a pointer to the first matching node in preorder, searching left before right, or NULL if none exists. Checking the current node first makes a root match immediate. Otherwise, search the left subtree; if it succeeds, return that pointer without entering the right subtree. Search right only when left fails.

That early return is sound because finding any match establishes that the target exists. Returning NULL merely because the current node does not match would be unsound: its descendants remain unexamined. The same distinction applied to BFS in the previous lesson.

The video returns a boolean; your C version will return a node pointer. That preserves the location of the match and lets the test distinguish the two nodes containing 5.

Implement both functions in C

Save the following as tree.c. Replace the two TODO bodies, leaving the tests unchanged. Spend roughly 3 minutes stating each function’s contract and empty-tree result, 15 minutes coding, and 4 minutes compiling and checking edge cases.

The input is assumed to be a valid, acyclic binary tree whose nodes remain alive during the call. Values and tree size are small enough that every addition fits in int64_t; overflow handling is outside this traversal task. Neither function should modify a node.

#include <assert.h>
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

/* Return the first preorder match, left subtree before right; else NULL. */
static const Node *find_value(const Node *root, int target)
{
    /* TODO */
}

/* Return the sum of all values in this subtree. */
static int64_t sum_values(const Node *root)
{
    /* TODO */
}

int main(void)
{
    Node n3 = {-4, NULL, NULL};
    Node n4 = { 5, NULL, NULL};
    Node n5 = { 5, NULL, NULL};
    Node n6 = { 9, NULL, NULL};
    Node n1 = { 3, &n3, &n4};
    Node n2 = {12, &n5, &n6};
    Node n0 = { 7, &n1, &n2};

    assert(find_value(&n0, 7) == &n0);
    assert(find_value(&n0, 5) == &n4); /* left match wins */
    assert(find_value(&n0, 9) == &n6);
    assert(find_value(&n0, 99) == NULL);
    assert(find_value(NULL, 5) == NULL);

    assert(sum_values(&n0) == 37);
    assert(sum_values(&n3) == -4);
    assert(sum_values(NULL) == 0);

    puts("Tree tests passed");
    return 0;
}

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
  -fsanitize=address,undefined tree.c -o tree
./tree

The nodes are constructed as local objects in main, so a returned pointer remains valid throughout these tests. In a different program, the caller must ensure the tree outlives any pointer returned by find_value.

Review the return paths and complexity

Compare your implementations with these replacements for the TODO bodies:

static const Node *find_value(const Node *root, int target)
{
    if (root == NULL)
        return NULL;
    if (root->value == target)
        return root;

    const Node *found = find_value(root->left, target);
    if (found != NULL)
        return found;

    return find_value(root->right, target);
}

static int64_t sum_values(const Node *root)
{
    if (root == NULL)
        return 0;

    int64_t left_sum = sum_values(root->left);
    int64_t right_sum = sum_values(root->right);
    return (int64_t)root->value + left_sum + right_sum;
}

The search’s found variable is a result from the whole left subtree, not just the left child. That is why returning it immediately preserves the specified left-first behavior. If it is NULL, the right subtree is still unresolved. Conversely, the sum must obtain both child results even if one is zero or negative.

Let $n$ be the number of nodes, and let $h$ be the number of nodes on the longest root-to-leaf path. sum_values visits every node, so it takes $O(n)$ time. find_value can stop at the root, but its worst case is also $O(n)$, for example when the target is absent. Each recursive call holds a small amount of state, and at most one root-to-leaf chain of calls is active at once: both functions use $O(h)$ auxiliary stack space. That is $O(\log n)$ for a balanced tree and $O(n)$ for a chain-shaped tree. Unlike the graph traversal last lesson, neither needs a visited array—provided the input really is a tree.

Key takeaways

For a binary-tree problem, first define the subtree contract and the empty-tree result. A search can check the current node before descending and return as soon as it finds a match. An aggregation commonly waits for both child results, then combines them at the parent. Both patterns take linear time in the worst case; recursive space depends on tree height.

Next you’ll use a heap for top-$k$ and streaming-selection problems. Unlike today’s tree, a heap imposes a value-ordering rule that lets you avoid scanning every item for certain queries.