Binary trees

In this article i'm going to talk about binary trees. Binary tree is a data structure where each node have at most two children(other nodes), usually it's left child and right child

Sometimes it's possible to interpret binary trees as undirected or directed graph, in this case binary tree is ordered or rooted tree. Indeed, that binary tree is a type of M-ary tree, where M is 2.

Using of binary trees in programming

• Representation of data with bifurcating structure(rus. разветвляющаяся структура), common use cases: Huffman coding
• Using for searching and sorting as they provide hierarchical data storage

Types of binary trees

I should say that tree terminology is not well-standardized and it could differ, especially if you'll open old books

• a perfect binary tree: all interior nodes have 2 children and leaves have the same depth. An example of perfect tree is family tree, becuase all people have two parents.
• a degenerate binary tree: every node has only one chlid, so tree will behave as linked list
• a full binary tree: type of binary tree in which every node has 0 or 2 children. A full binary tree also is:

• a complete binary tree: binary tree, in which level, except lpossibly ast, is completely filled and all nodes as far left as possible
• a balanced binary tree: binary tree in which left and right subtrees of every nodes differ in height no more than 1

Properties of binary trees

Some obvious facts

• the minimum number of nodes at height H = H + 1
• the maximum number of nodes at height H = 2^H - 1
• the maximum number of nodes at any level(n) = 2^n
• minimum possible hieghts or levels = log2(n + 1)

if you want to see other properties you're free to visit wiki

Methods for storing binary trees

• using of references and nodes
• using of arrays(this one benefits from more compact storage and better locality to references)

Implementation

I'll implement solution in c++. I've done Search Binary tree, it's a little bit complicated, because we need to add elements in tree according to certain rules.

C++ solution of binary search tree

Creating structure for node, it's basically data, pointer to next left node and next right node. Also here is two constructions.

struct Node { 
    int data; 
    Node* left; 
    Node* right; 
    Node(int data) { 
        this->data = data; 
        left = nullptr; 
        right = nullptr; 
    }
    Node() { 
        data = 0; 
        left = nullptr; 
        right = nullptr; 
    }
};

This is class Binary_tree, which defines some functions for adding elements, printing in different order and destroing tree.

class Binary_tree 
{
private: 
    Node* root; 
    void destroy(Node* leaf); 
    void insert(int key, Node* leaf); 
    void inorder_print(Node* leaf); 
    void preorder_print(Node* leaf); 
    void postorder_print(Node* leaf); 
    Node* search(int key, Node* leaf);
public: 
    Binary_tree(); 
    void insert(int key); 
    void destroy(); 
    void inorder_print(); 
    void preorder_print(); 
    void postorder_print(); 
    Node* search(int key);};

Let's start from insert function. Code is well-commented, so you don't actually need my comments

void Binary_tree::insert(int key, Node* leaf) {
    if (key < leaf->data) { 
        // if leaf->right isn't a leaf, than go to the next and check 
        if (leaf->left != nullptr)
            insert(key, leaf->left); 
        // if it is a leaf, than create a new object 
        // and initialize data with key 
        else { 
            leaf->left = new Node(); 
            leaf->left->data = key; 
        } 
    } 
    else if (key >= leaf->data) { 
        // if leaf->right isn't a leaf, than go to the next and check 
        if (leaf->right != nullptr)
            insert(key, leaf->right); 
        // if it is a leaf, than create a new object 
        // and initialize data with key 
        else { 
            leaf->right = new Node(); 
            leaf->right->data = key; 
        } 
    }
}

Next function is destroy. It's pretty simple.

void Binary_tree::destroy(Node* leaf) {
    if (leaf != nullptr) { 
        destroy(leaf->left); 
        destroy(leaf->right); 
        delete leaf; 
    }
}

The last complicated function is search function.

Node* Binary_tree::search(int key, Node* leaf) { 
    if (leaf != nullptr) { 
        if (leaf->data == key) 
            return leaf; 
        else if (key > leaf->data) 
            return search(key, leaf->right); 
        else 
            return search(key, leaf->left); 
    } 
    else 
        return nullptr; // there are no elements in Binary_tree
}

Next important thing is different types of traversing tree, it means visiting and outputing all values of each node in particular order.

Each of traversing methods have a particular order they follow

• For Inorder, you traverse from the left subtree to the root then to the right subtree.
• For Preorder, you traverse from the root to the left subtree then to the right subtree.
• For Post order, you traverse from the left subtree to the right subtree then to the root.

Let's have a look at code.

// left - > root - > right
void Binary_tree::inorder_print(Node* leaf) { 
    if (leaf != nullptr) { 
        inorder_print(leaf->left); 
        std::cout << leaf->data << " "; 
        inorder_print(leaf->right); 
    }
}

// root - > left - > right
void Binary_tree::preorder_print(Node* leaf) { 
    if (leaf != nullptr) { 
        std::cout << leaf->data << " "; 
        inorder_print(leaf->left); 
        inorder_print(leaf->right); 
    }
}

// left - > right - > root
void Binary_tree::postorder_print(Node* leaf) { 
    if (leaf != nullptr) { 
        inorder_print(leaf->left); 
        inorder_print(leaf->right); 
        std::cout << leaf->data; 
    }
}

I won't comment my public methods, it's done for encapsulation and mostly they just call private functions.

Full code at my GitHub profile: https://github.com/rastr-0/Simple_algorithms/blob/master/binary_tree/binary_tree.cpp

See ya soon

@rastr