Binary Trees

A binary tree is a data structure in which each node has at most two children, which are referred to as the left child and the right child. Binary trees are used to implement various data structures, including binary search trees, heaps, and syntax trees.

Structure

A binary tree is defined recursively as a structure consisting of a node, which contains a value and two references to its left and right children. The children themselves are also binary trees. A binary tree can be represented in code as follows:

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

Types of Binary Trees

There are several types of binary trees with different properties:

• Full binary tree: Every level of the tree is completely filled except possibly for the last level, which is filled from left to right.
• Complete binary tree: Every level of the tree is completely filled, and all nodes are as far left as possible.
• Balanced binary tree: The height of the tree is minimized, ensuring that operations on the tree are efficient.
• Binary search tree (BST): For each node, all elements in the left subtree are less than the node's value, and all elements in the right subtree are greater than the node's value.

Traversals

There are several ways to traverse a binary tree:

• Preorder traversal: Visit the current node, then traverse the left subtree, and finally traverse the right subtree.
• Inorder traversal: Traverse the left subtree, visit the current node, and then traverse the right subtree.
• Postorder traversal: Traverse the left subtree, traverse the right subtree, and then visit the current node.

Example: Binary Search Tree

A binary search tree is a binary tree with the additional property that the value of each node is greater than or equal to the values of all nodes in its left subtree and less than or equal to the values of all nodes in its right subtree.

Here is a C++ example of a simple binary search tree:

#include <iostream>

struct TreeNode {
    int value;
    TreeNode * left;
    TreeNode * right;

    TreeNode(int val): value(val), left(nullptr), right(nullptr) {}
};

class BinaryTree {
    public: TreeNode * root;

    BinaryTree(): root(nullptr) {}

    void insert(int data) {
        if (root == nullptr) {
            root = new TreeNode(data);
        } else {
            insertHelper(root, data);
        }
    }

    private: void insertHelper(TreeNode * node, int data) {
        if (data < node -> value) {
            if (node -> left == nullptr) {
                node -> left = new TreeNode(data);
            } else {
                insertHelper(node -> left, data);
            }
        } else {
            if (node -> right == nullptr) {
                node -> right = new TreeNode(data);
            } else {
                insertHelper(node -> right, data);
            }
        }
    }
};

int main() {
    BinaryTree tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(1);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);

    // The tree structure is now:
    //         5
    //       /   \
    //      3     7
    //     / \   / \
    //    1   4 6   8

    return 0;
}

In this example, we create a binary search tree and insert nodes with the values 5, 3, 7, 1, 4, 6, and 8. The structure of the tree is as shown in the comments.

Traversal Methods

There are three common ways to traverse a binary tree: inorder, preorder, and postorder traversal. Each traversal method visits nodes in a different order, and the choice of which traversal to use depends on the problem being solved.

Inorder Traversal

In an inorder traversal, the left subtree is visited first, followed by the current node, and then the right subtree. This traversal results in visiting the nodes in sorted order for a binary search tree.

Example:

void inorderTraversal(Node* node) {
    if (node) {
        inorderTraversal(node->left);
        cout << node->data << " ";
        inorderTraversal(node->right);
    }
}

Preorder Traversal

In a preorder traversal, the current node is visited first, followed by the left subtree and then the right subtree.

Example:

void preorderTraversal(Node* node) {
    if (node) {
        cout << node->data << " ";
        preorderTraversal(node->left);
        preorderTraversal(node->right);
    }
}

Postorder Traversal

In a postorder traversal, the left subtree is visited first, followed by the right subtree, and then the current node.

Example:

void postorderTraversal(Node* node) {
    if (node) {
        postorderTraversal(node->left);
        postorderTraversal(node->right);
        cout << node->data << " ";
    }
}

Related USACO Problems

• USACO 2017 January Contest, Silver - Problem 3. Hoofball