Building Min-Max Trees with Bottom-Up Algorithms

The Build Strategy: Recursive Post-Order Traversal

The most intuitive way to build our tree is using a recursive algorithm that performs a post-order traversal. The term "bottom-up" in the learning outcome refers to the order of computation. While the function calls proceed "top-down" through the tree structure, the actual values are computed "bottom-up":

1. A parent node can only be computed after its children have been computed.
2. This process continues until we reach the root, which is computed last.

Let's visualize the final structure we're aiming to build.

The build process will recursively divide the input array until it reaches single-element ranges (the leaves), and then on the way back up the recursion stack, it will combine the results to populate the parent nodes.

To see a detailed, step-by-step walkthrough of this exact recursive process, let's turn back to the excellent video by Tushar Roy.

Implementing the Recursive Build in C++

Now, let's translate this logic into C++ within our MinMaxTree class. We'll start with the class structure we designed last time and fill in the build functionality.

A key best practice, also shown in the competitive programming resources, is to create a combine helper function. This isolates the logic for merging two child nodes into a parent node. For our min-max tree, this function is straightforward.

// Within the MinMaxTree class
private:
    struct MinMaxNode {
        T min_val;
        T max_val;
    };

    // Helper to merge two child nodes into a parent
    MinMaxNode combine(const MinMaxNode& left, const MinMaxNode& right) {
        return {
            std::min(left.min_val, right.min_val),
            std::max(left.max_val, right.max_val)
        };
    }

With this helper, our main recursive build function becomes cleaner. It takes the input data, the index of the current tree node we're building, and the start and end indices of the data range this node represents.

// The private recursive build function
void build(const std::vector<T>& data, size_t node_idx, size_t range_start, size_t range_end) {
    // Base case: If the range is a single element, we're at a leaf
    if (range_start == range_end) {
        m_tree[node_idx] = {data[range_start], data[range_start]};
        return;
    }

    // Recursive step:
    // 1. Find the midpoint to split the range
    size_t mid = range_start + (range_end - range_start) / 2;
    
    // Define child indices based on 0-based array indexing
    size_t left_child_idx = 2 * node_idx + 1;
    size_t right_child_idx = 2 * node_idx + 2;

    // 2. Recursively build the left and right children
    build(data, left_child_idx, range_start, mid);
    build(data, right_child_idx, mid + 1, range_end);

    // 3. Combine the results from children into the current node (post-order step)
    m_tree[node_idx] = combine(m_tree[left_child_idx], m_tree[right_child_idx]);
}

A Note on Indexing: The video and some online resources use 1-based indexing for the tree array (2*v and 2*v+1 for children). Since we are using a std::vector, 0-based indexing is more natural. The formulas for a 0-indexed node at index i are:

• Left Child: 2 * i + 1
• Right Child: 2 * i + 2
• Parent: (i - 1) / 2

Finally, we tie this all together in the public constructor of our class. The constructor will size the tree vector appropriately and kick off the recursion from the root node (index 0), which covers the entire data range (0 to n-1).

public:
    // Constructor
    MinMaxTree(const std::vector<T>& data) {
        if (data.empty()) {
            m_num_leaves = 0;
            return;
        }
        
        m_num_leaves = data.size();
        
        // Allocate 4*n space. This is a safe upper bound for the tree size.
        m_tree.resize(4 * m_num_leaves);
        
        // Start the recursive build from the root node (index 0)
        build(data, 0, 0, m_num_leaves - 1);
    }

The article on cp-algorithms.com provides a complete example of this structure for a slightly different problem (finding max and its count), which is excellent further reading.

An Alternative: The Iterative Bottom-Up Build

The recursive approach is clear and directly models the tree structure. However, in the spirit of high-performance engineering, it's valuable to know that a non-recursive, iterative solution also exists. This approach can be slightly faster by avoiding the function call overhead of deep recursion.

The logic is elegantly simple and truly "bottom-up":

1. Allocate a tree array of size 2 * n (where n is the input size, assuming power-of-two for simplicity, or 2 * next_power_of_2(n)).
2. Copy the n input data points directly into the second half of the tree array (the leaves).
3. Iterate backwards from the last parent node down to the root, calculating each parent's value from its two children, which have already been computed.

Let's look at a resource that implements this.

Here's how we could adapt that iterative approach to our MinMaxTree (as a conceptual alternative):

// Alternative iterative constructor
MinMaxTree(const std::vector<T>& data) {
    if (data.empty()) return;
    
    m_num_leaves = data.size();
    // For this method, size is 2*n
    m_tree.resize(2 * m_num_leaves);
    
    // 1. Copy data to the leaf nodes
    for (size_t i = 0; i < m_num_leaves; ++i) {
        m_tree[m_num_leaves + i] = {data[i], data[i]};
    }
    
    // 2. Build the rest of the tree bottom-up
    for (int i = m_num_leaves - 1; i > 0; --i) {
        // Here, child indices are 2*i and 2*i + 1 due to the specific layout
        m_tree[i] = combine(m_tree[2 * i], m_tree[2 * i + 1]);
    }
}

While we will proceed with the recursive implementation because it's more flexible for non-power-of-two input sizes, understanding this iterative method is a valuable insight into data-oriented algorithm design. It transforms a tree problem into simple, linear passes over an array.

Conclusion

Today we have successfully moved from a data structure design to a working implementation. We have written the code that constructs our min-max tree from an initial dataset.

Key Takeaways:

• We implemented a recursive, post-order traversal algorithm (build) to populate our min-max tree.
• The algorithm's base case handles leaf nodes (single data points), and the recursive step merges results from child nodes to compute parent nodes.
• The use of a combine helper function keeps the logic clean and modular.
• We explored an iterative bottom-up approach as a performant alternative that avoids recursion, reinforcing data-oriented design principles.

Our MinMaxTree class can now take data and organize it. The structure is built, but we haven't used it yet.

What's Next?

With the tree built, the next crucial step is to query it. In our next lesson, we will implement the getMinMaxInRange function. This will fulfill the core purpose of the data structure: finding the minimum and maximum values over an arbitrary range in our dataset with logarithmic time complexity, O(log n). This is where the performance payoff for all this setup work will become clear.