Trees and Binary Trees

Data with branches

A tree branches: one item at the top, and each item can have items below it.

Think of it like this: A family tree, folders on your computer, or a company chart with the CEO at the top.

Binary trees

In a binary tree each node has at most a left and a right child:

#include <iostream>
using namespace std;

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

int main() {
    /*        1
             / \
            2   3
           / \
          4   5      */
    Node* root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    cout << root->value << " " << root->left->value << " " << root->right->value << endl;
    cout << "children of 2: " << root->left->left->value << " " << root->left->right->value << endl;
    return 0;
}

Output

1 2 3
children of 2: 4 5

Remember: Every subtree is a tree. That's why recursion fits trees so well: solve left, solve right, combine.