13. Binary Trees in C++

Salam Elshad

What is a Binary Tree?

A Binary Tree is a type of data structure that holds elements in a sorted manner. The data in a binary tree is stored in nodes, each node having a maximum of two children, known as the left child and the right child. The topmost element is known as the root of the tree.

Key Points:

• The root node is the first element in the tree.

• Each node in a binary tree has a maximum of two child nodes.

• The left child node contains elements smaller than the parent node.

• The right child node contains elements larger than the parent node.

Advantages of Binary Trees

The primary advantage of binary trees over other data storage structures is that data is stored sequentially, making the search process faster. Searching for an element in a binary tree is easier due to its sorted nature.

Height and Degree in Binary Tree

In a binary tree, the concept of 'Height' and 'Degree' is essential.

• The Height of a binary tree is the length of the longest path from the root to a leaf. It is also referred to as the 'Depth' of the tree.

• The Degree of a node is the number of children it has. In a binary tree, the degree can be 0, 1, or 2.

Big O Notation in Binary Trees

The time complexity for searching, inserting, and deleting operations in a binary tree is O(log(n)) in the best case scenario. This is because these operations can skip about half of the tree, thus the complexity is logarithmic in the number of tree nodes 'n'.

Insertion Operation

Insertion operation in a binary tree is faster compared to other data structures. The new element is always inserted at a leaf node.

Code Example

Below is a simple implementation of a binary tree in C++:

struct Node {
    int data;
    Node* left;
    Node* right;
};

// Function to create a new Node in heap
Node* GetNewNode(int data) {
    Node* newNode = new Node();
    if (!newNode) {
        cout << "Memory error\\n";
        return NULL;
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// To insert data in a node
Node* insert(Node* root, int data) {
    // if tree is empty assign the new node address to root
    if (root == NULL) {
        root = GetNewNode(data);
    }
    // else, do a recursive call to insert the data
    else if (data <= root->data) {
        root->left = insert(root->left, data);
    }
    else {
        root->right = insert(root->right, data);
    }

    return root;
}

This code creates a new node GetNewNode, and a function insert to insert a new node in the binary tree.

Each node in a binary tree includes data, and pointers to left and right child nodes. The insert function is used to add new nodes to the tree. The new data is always inserted at a leaf.

Reference

The content in this document is based on the original notes provided in Azerbaijani. For further details, you can refer to the original document using the following link:

Original Note - Azerbaijani Version