Binary Tree in Data Structure

A Binary Tree is a form of Tree Data Structure with almost two children for every node. This is required to store the data in a hierarchical form, unlike linear data structures.

1. Introduction

A simple Binary Tree is not useful for real-time applications, but it is a foundation to implement the other trees such as Binary Search Tree, AVL Tree, Red-Black Tree, and Splay Tree. However, the sample implementation provided in this article is useful for the educative purpose.

Representation

// Binary Tree node representation
struct Node
{
    int data;    // Actual data
    Node* left;  // Pointer to left child
    Node* right; // Pointer to right child

    // Node constructor
    Node(int d) : data(d), left(NULL), right(NULL) {}
};

// The root node
Node* root;

Applications

• A simple Binary Tree is not useful for real-time applications, because of its Time Complexity. Since the data elements are not sorted in a particular order, the search, insertion, and deletion operations work in O(n) time.
• However, it is used to implement the other forms of Binary Trees useful for applications. This includes Binary Search Tree, AVL Tree, Red-Black Tree, Splay Tree, and Heaps.

2. Insertion on Binary Tree

In a Binary Tree, a new node is inserted at the last position. The position can be identified by traversing the tree in level order. We find a node with either its Left or Right child empty and insert a new node.

Algorithm

1. Create the new Node with the data and initialize its Left and Right child to NULL.
2. Traverse the tree in Levelorder (10, 20, 30, 40, 50 in the above tree).
3. Find the first node with either its Left or Right child is free.
4. Link the new node to the free position.

Code

// Insert a node in the deepest location
Node* BinaryTree::insert(int data)
{
    // Check if the tree is empty. If so, insert the node at the root.
    if (root == NULL) {
        root = new Node(data);
        return root;
    }

    // Traverse the tree in level order to insert in the deepest location. 
    std::queue<Node*> q;
    q.push(root);
    while (! q.empty()) {
        Node* p = q.front();
        q.pop();

        if (p->left == NULL) {
            p->left = new Node(data);
            return p->left;
        } else {
            q.push(p->left);
        }

        if (p->right == NULL) {
            p->right = new Node(data);
            return p->right;
        } else {
            q.push(p->left);
        }
    }
}

Examples

Here are the examples of inserting the data 10, 20, 30, 40, and 50 in a Binary Tree.

3. Deletion on Binary Tree

A node can not be deleted straight away from the tree because it may have children. So, the easiest way is to replace the node’s data with the deepest node. Finally, delete the deepest node as it does not have any children.

Algorithm

1. Check the tree is empty and return if true
2. Check the tree has only a single node and matches the given data. If true, delete the node, set the root to NULL, and return.
3. Otherwise, traverse the tree in Levelorder starting from the root node.
4. Search the target node that contains the given data.
5. Continue the traversal to locate the deepest node.
6. Replace the target node with the deepest node’s data.
7. Delete the deepest node.

Code

/ Delete the node by the given data
void BinaryTree::remove(int data)
{
    // Check the tree is empty and return if true
    if (root == NULL) {
        return;
    }

    // Check the tree has only a single node.
    if (root->left == NULL && root->right == NULL) {
        // Check if the root node matches the given data.
        if (root->data == data) {
            // Delete the root node
            delete root;
            root = NULL;
        }
        return;
    }

    Node *target = NULL; // Node requested for deletion
    Node* p = NULL;      // Last node of the tree
    Node *pp = NULL;     // Parent of last node

    // Traverse the tree in level order
    std::queue<Node*> q;
    q.push(root);
    while (! q.empty()) {
        p = q.front();
        q.pop();

        if (p->data == data) {
            // Found the target node, proceed to find the last node
            target = p;
        }
        if (p->left != NULL) {
            pp = p;
            q.push(p->left);
        }
        if (p->right != NULL) {
            pp = p;
            q.push(p->right);
        }
    }

    // Replace the target node with the last node's data and delete the last node
    if (target != NULL) {
        target->data = p->data;
        if (pp->left == p) {
            pp->left = NULL;
        } else {
            pp->right = NULL;
        }
        delete p;
    }
}

Examples

1. Delete node (20) from the Binary Tree

2. Delete node (10)

4. Search on Binary Tree

Searching the data in Binary Tree can be made simple using recursive calls. Start the search from the root node, search the left subtree, and search the right subtree. This process can be repeated for every node until the node is found.

Algorithm

1. Check if the tree is empty and return NULL.
2. Check if the current node matches the data and return the node if true.
3. Perform the recursive call to search on the left subtree and return the node if found.
4. Perform the recursive call to search on the right subtree and return the node if found.

Code

// Search the node by the given data
Node* BinaryTree::search(int data, Node* root)
{
    // Check if the tree is empty and return
    if (root == NULL) {
        return NULL;
    }

    // Check if the current node matches the data and return the node if true.
    if (root->data == data) {
        return root;
    }

    // Search on the left sub tree and return the node if found.
    Node* target = search(data, root->left);
    if (target != NULL) {
        return target;
    }

    // Search on the right sub tree and return the node if found.
    target = search(data, root->right);
    return target;
}

5. Traversals on Binary Tree

A Binary Tree can be traversed in any one of the following orders.

• Preorder (Root, Left, Right)
• Postorder (Left, Right, Root)
• Inorder (Left, Root, Right)
• Levelorder (Level 0, Level 1, and so on.)

5.1 Preorder Traversal

Traverse the tree in the order of Root, left, and right subtree.

// Traverse the tree in preorder (parent, left, right)
void BinaryTree::traverse_preorder(Node* p)
{
    if (p != NULL) {
        cout << p->data << endl;
        traverse_preorder(p->left);
        traverse_preorder(p->right);
    }
}

5.2 Postorder Traversal

Traverse the tree in the order of left subtree, right subtree, and Root node.

// Traverse the tree in postorder (left, right, parent)
void BinaryTree::traverse_postorder(Node* p)
{
    if (p != NULL) {
        traverse_postorder(p->left);
        traverse_postorder(p->right);
        cout << p->data << endl;
    }
}

5.3 Inorder Traversal

Traverse the tree in the order of the left subtree, the Root node, and the right subtree.

// Traverse the tree inorder (left, parent, right)
void BinaryTree::traverse_inorder(Node* p)
{
    if (p != NULL) {
        traverse_inorder(p->left);
        cout << p->data << endl;
        traverse_inorder(p->right);
    }
}

5.4 Levelorder Traversal

Traverse the tree in the breadth-first approach. The std::queue data structure is used here to traverse the tree in the order of level 0, level 1, and so on.

// Traverse the tree in level order (breadth first)
void BinaryTree::traverse_levelorder(Node* p)
{
    if (p == NULL) {
        return;
    }

    // Start the traversal from root node
    std::queue<Node*> q;
    q.push(root);

    while (! q.empty()) {
        Node* p = q.front();
        q.pop();

        // Visit the current node
        cout << p->data << endl;

        // Enqueue the left and right child to process in order.
        if (p->left != NULL) {
            q.push(p->left);
        }
        if (p->right != NULL) {
            q.push(p->right);
        }
    }
}

6. Implementation of Binary Tree in C++

/**
 * C++ example to demonstrate the Binary Tree
 */
#include <iostream>
#include <queue>
using namespace std;

// Binary Tree node representation
struct Node
{
    int data;    // Actual data
    Node* left;  // Pointer to left child
    Node* right; // Pointer to right child

    // Node constructor
    Node(int d) : data(d), left(NULL), right(NULL) {}
};

/**
 * Binary Tree implementation
 */
class BinaryTree
{
    // The root node
    Node* root;

public:
    // Constructor
    BinaryTree() : root(NULL) {}

    // Get the root node
    Node* get_root() { return root; }

    // Insert a node in the deepest location
    // Returns the node inserted
    Node* insert(int data);

    // Delete the node by the given data
    void remove(int data);

    // Search the node by the given data
    Node* search(int data, Node* root);
    
    // Preorder traversal
    void traverse_preorder(Node* p);

    // Postorder traversal
    void traverse_postorder(Node* p);

    // Inorder traversal
    void traverse_inorder(Node* p);

    // Levelorder traversal
    void traverse_levelorder(Node* p);
};

// Insert a node in the deepest location
Node* BinaryTree::insert(int data)
{
    // Check if the tree is empty. If so, insert the node at the root.
    if (root == NULL) {
        root = new Node(data);
        return root;
    }

    // Traverse the tree in level order to insert in the deepest location. 
    std::queue<Node*> q;
    q.push(root);
    while (! q.empty()) {
        Node* p = q.front();
        q.pop();

        if (p->left == NULL) {
            p->left = new Node(data);
            return p->left;
        } else {
            q.push(p->left);
        }

        if (p->right == NULL) {
            p->right = new Node(data);
            return p->right;
        } else {
            q.push(p->left);
        }
    }
}

// Delete the node by the given data
void BinaryTree::remove(int data)
{
    // Check the tree is empty and return if true
    if (root == NULL) {
        return;
    }

    // Check the tree has only a single node.
    if (root->left == NULL && root->right == NULL) {
        // Check if the root node matches the given data.
        if (root->data == data) {
            // Delete the root node
            delete root;
            root = NULL;
        }
        return;
    }

    Node *target = NULL; // Node requested for deletion
    Node* p = NULL;      // Last node of the tree
    Node *pp = NULL;     // Parent of last node

    // Traverse the tree in level order
    std::queue<Node*> q;
    q.push(root);
    while (! q.empty()) {
        p = q.front();
        q.pop();

        if (p->data == data) {
            // Found the target node, proceed to find the last node
            target = p;
        }
        if (p->left != NULL) {
            pp = p;
            q.push(p->left);
        }
        if (p->right != NULL) {
            pp = p;
            q.push(p->right);
        }
    }

    // Replace the target node with the last node's data and delete the last node
    if (target != NULL) {
        target->data = p->data;
        if (pp->left == p) {
            pp->left = NULL;
        } else {
            pp->right = NULL;
        }
        delete p;
    }
}

// Search the node by the given data
Node* BinaryTree::search(int data, Node* root)
{
    // Check if the tree is empty and return
    if (root == NULL) {
        return NULL;
    }

    // Check if the current node matches the data and return the node if true.
    if (root->data == data) {
        return root;
    }

    // Search on the left sub tree and return the node if found.
    Node* target = search(data, root->left);
    if (target != NULL) {
        return target;
    }

    // Search on the right sub tree and return the node if found.
    target = search(data, root->right);
    return target;
}

// Traverse the tree in preorder (parent, left, right)
void BinaryTree::traverse_preorder(Node* p)
{
    if (p != NULL) {
        cout << p->data << endl;
        traverse_preorder(p->left);
        traverse_preorder(p->right);
    }
}

// Traverse the tree in postorder (left, right, parent)
void BinaryTree::traverse_postorder(Node* p)
{
    if (p != NULL) {
        traverse_postorder(p->left);
        traverse_postorder(p->right);
        cout << p->data << endl;
    }
}

// Traverse the tree inorder (left, parent, right)
void BinaryTree::traverse_inorder(Node* p)
{
    if (p != NULL) {
        traverse_inorder(p->left);
        cout << p->data << endl;
        traverse_inorder(p->right);
    }
}

// Traverse the tree in level order (breadth first)
void BinaryTree::traverse_levelorder(Node* p)
{
    if (p == NULL) {
        return;
    }

    // Start the traversal from root node
    std::queue<Node*> q;
    q.push(root);

    while (! q.empty()) {
        Node* p = q.front();
        q.pop();

        // Visit the current node
        cout << p->data << endl;

        // Enqueue the left and right child to process in order.
        if (p->left != NULL) {
            q.push(p->left);
        }
        if (p->right != NULL) {
            q.push(p->right);
        }
    }
}

int main()
{
    /** Create a binary tree and insert data
     *           10
     *         /    \
     *        20    30
     *      /    \
     *     40    50
     */
    BinaryTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(40);
    tree.insert(50);

    // Search
    Node* p = tree.search(30, tree.get_root());
    cout << "Search(30) located node: " << p->data << endl;

    // Traversals
    cout << "Binary Tree preorder traversal" << endl;
    tree.traverse_preorder(tree.get_root());
    cout << "Binary Tree inorder traversal" << endl;
    tree.traverse_inorder(tree.get_root());
    cout << "Binary Tree postorder traversal" << endl;
    tree.traverse_postorder(tree.get_root());
    cout << "Binary Tree level order traversal" << endl;
    tree.traverse_levelorder(tree.get_root());

    // Delete data
    tree.remove(20);
    tree.remove(10);
    cout << "Binary Tree level order traversal" << endl;
    tree.traverse_levelorder(tree.get_root());
}

Output

Search(30) located node: 30
Binary Tree preorder traversal
10
20
40
50
30
Binary Tree inorder traversal
40
20
50
10
30
Binary Tree postorder traversal
40
50
20
30
10
Binary Tree level order traversal
10
20
30
40
50
Binary Tree level order traversal
40
50
30

7. References

• Binary Tree Wiki