Measuring a Tree with Recursion

The recipe for tree recursion

• If the node is nullptr, return the answer for an empty tree.
• Ask the same question about the left and right subtrees.
• Combine the two answers with the current node.

#include <algorithm>
#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *left, *right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : value(v), left(l), right(r) {}
};

int height(Node* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }
int count(Node* n)  { return n ? 1 + count(n->left) + count(n->right) : 0; }
int total(Node* n)  { return n ? n->value + total(n->left) + total(n->right) : 0; }
int leaves(Node* n) {
    if (!n) return 0;
    if (!n->left && !n->right) return 1;
    return leaves(n->left) + leaves(n->right);
}

int main() {
    Node* root = new Node(8, new Node(3, new Node(1), new Node(6, new Node(4))), new Node(10, nullptr, new Node(14)));
    cout << "height: " << height(root) << endl;
    cout << "nodes:  " << count(root) << endl;
    cout << "sum:    " << total(root) << endl;
    cout << "leaves: " << leaves(root) << endl;
    return 0;
}

Output

height: 4
nodes:  7
sum:    46
leaves: 3

Each function visits every node once: O(n) time, and O(height) memory for the recursion.