Difference between Binary tree and B-tree

B-Tree : B-Tree is known as a self-balancing tree as its nodes are sorted in the inorder traversal. Unlike the binary trees, in B-tree, a node can have more than two children. B-tree has a height of logM N (Where ‘M’ is the order of tree and N is the number of nodes). And the height is adjusts automatically at each update. In the B-tree data is sorted in a specific order, with the lowest value on the left and the highest value on the right. To insert the data or key in B-tree is more complicated than binary tree.

There are some conditions that must be hold by the B-Tree:

All the leaf nodes of the B-tree must be at the same level.
Above the leaf nodes of the B-tree, there should be no empty sub-trees.
B- tree’s height should lie as low as possible.

Code:

Binary Tree : A binary tree is the special type of general tree. Unlike B-tree, in a binary tree a node can have at most two nodes. In a binary tree, there is a limitation on the degree of a node because the nodes in a binary tree can’t have more than two child node(or degree two). The topmost node of a binary tree is called root node and there are mainly two subtrees one is left-subtree and another is right-sub-tree. Unlike the general tree, the binary tree can be empty. Like B-tree, binary tree can also be sorted in inorder traversal. But it can also be sorted in preorder as well as postorder. In binary tree, data insertion is not complicated than B-tree.

Code:

C++

#include <iostream>
#include <queue> // Include this to use queue
using namespace std;

// Define the structure for nodes in the Binary Tree
struct Node {
    char data;
    Node* left;
    Node* right;
};

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

// Function to insert nodes in level order
Node* insertNode(Node* root, char data, queue<Node*>& q)
{
    Node* newNode = createNode(data);
    if (root == NULL)
        root = newNode;
    else if (q.front()->left == NULL)
        q.front()->left = newNode;
    else {
        q.front()->right = newNode;
        q.pop();
    }

    q.push(newNode);
    return root;
}

// Function to print the tree in inorder traversal
void inorder(Node* temp)
{
    if (temp == NULL)
        return;

    inorder(temp->left);
    cout << temp->data << ' ';
    inorder(temp->right);
}

// Function to print the tree in preorder traversal
void preorder(Node* temp)
{
    if (temp == NULL)
        return;

    cout << temp->data << ' ';
    preorder(temp->left);
    preorder(temp->right);
}

// Function to print the tree in postorder traversal
void postorder(Node* temp)
{
    if (temp == NULL)
        return;

    postorder(temp->left);
    postorder(temp->right);
    cout << temp->data << ' ';
}

int main()
{
    Node* root = createNode('A');
    queue<Node*> q;
    q.push(root);
    root = insertNode(root, 'B', q);
    root = insertNode(root, 'C', q);
    root = insertNode(root, 'D', q);
    root = insertNode(root, 'E', q);
    root = insertNode(root, 'F', q);
    root = insertNode(root, 'G', q);

    cout << "Inorder traversal: ";
    inorder(root);
    cout << "\nPreorder traversal: ";
    preorder(root);
    cout << "\nPostorder traversal: ";
    postorder(root);
    return 0;
}

Java

import java.util.LinkedList;
import java.util.Queue;

// Define the structure for nodes in the Binary Tree
class Node {
    char data;
    Node left, right;

    Node(char data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class BinaryTree {
    // Function to insert nodes in level order
    static Node insertNode(Node root, char data,
                           Queue<Node> q)
    {
        Node newNode = new Node(data);
        if (root == null)
            root = newNode;
        else if (q.peek().left == null)
            q.peek().left = newNode;
        else {
            q.peek().right = newNode;
            q.poll();
        }

        q.add(newNode);
        return root;
    }

    // Function to print the tree in inorder traversal
    static void inorder(Node temp)
    {
        if (temp == null)
            return;

        inorder(temp.left);
        System.out.print(temp.data + " ");
        inorder(temp.right);
    }

    // Function to print the tree in preorder traversal
    static void preorder(Node temp)
    {
        if (temp == null)
            return;

        System.out.print(temp.data + " ");
        preorder(temp.left);
        preorder(temp.right);
    }

    // Function to print the tree in postorder traversal
    static void postorder(Node temp)
    {
        if (temp == null)
            return;

        postorder(temp.left);
        postorder(temp.right);
        System.out.print(temp.data + " ");
    }

    public static void main(String[] args)
    {
        Node root = new Node('A');
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        root = insertNode(root, 'B', q);
        root = insertNode(root, 'C', q);
        root = insertNode(root, 'D', q);
        root = insertNode(root, 'E', q);
        root = insertNode(root, 'F', q);
        root = insertNode(root, 'G', q);

        System.out.print("Inorder traversal: ");
        inorder(root);
        System.out.print("\nPreorder traversal: ");
        preorder(root);
        System.out.print("\nPostorder traversal: ");
        postorder(root);
    }
}

Python

from collections import deque

# Define the structure for nodes in the Binary Tree


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to create a new node


def create_node(data):
    return Node(data)

# Function to insert nodes in level order


def insert_node(root, data, q):
    new_node = create_node(data)
    if root is None:
        root = new_node
    elif q[0].left is None:
        q[0].left = new_node
    else:
        q[0].right = new_node
        q.popleft()

    q.append(new_node)
    return root

# Function to print the tree in inorder traversal


def inorder(temp):
    if temp is None:
        return
    inorder(temp.left)
    print(temp.data, end=' ')
    inorder(temp.right)

# Function to print the tree in preorder traversal


def preorder(temp):
    if temp is None:
        return
    print(temp.data, end=' ')
    preorder(temp.left)
    preorder(temp.right)

# Function to print the tree in postorder traversal


def postorder(temp):
    if temp is None:
        return
    postorder(temp.left)
    postorder(temp.right)
    print(temp.data, end=' ')


# Main function
if __name__ == "__main__":
    root = create_node('A')
    q = deque()
    q.append(root)
    root = insert_node(root, 'B', q)
    root = insert_node(root, 'C', q)
    root = insert_node(root, 'D', q)
    root = insert_node(root, 'E', q)
    root = insert_node(root, 'F', q)
    root = insert_node(root, 'G', q)

    print("Inorder traversal: ", end='')
    inorder(root)
    print("\nPreorder traversal: ", end='')
    preorder(root)
    print("\nPostorder traversal: ", end='')
    postorder(root)

JavaScript

// Define the structure for nodes in the Binary Tree
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Function to insert nodes in level order
function insertNode(root, data, q) {
    let newNode = new Node(data);
    if (!root) {
        root = newNode;
    } else if (!q[0].left) {
        q[0].left = newNode;
    } else {
        q[0].right = newNode;
        q.shift();
    }
    q.push(newNode);
    return root;
}

// Function to print the tree in inorder traversal
function inorder(temp) {
    if (!temp) return;
    inorder(temp.left);
    process.stdout.write(temp.data + " ");
    inorder(temp.right);
}

// Function to print the tree in preorder traversal
function preorder(temp) {
    if (!temp) return;
    process.stdout.write(temp.data + " ");
    preorder(temp.left);
    preorder(temp.right);
}

// Function to print the tree in postorder traversal
function postorder(temp) {
    if (!temp) return;
    postorder(temp.left);
    postorder(temp.right);
    process.stdout.write(temp.data + " ");
}

// Main method
function main() {
    let root = new Node('A');
    let q = [root];
    root = insertNode(root, 'B', q);
    root = insertNode(root, 'C', q);
    root = insertNode(root, 'D', q);
    root = insertNode(root, 'E', q);
    root = insertNode(root, 'F', q);
    root = insertNode(root, 'G', q);

    process.stdout.write("Inorder traversal: ");
    inorder(root);
    process.stdout.write("\nPreorder traversal: ");
    preorder(root);
    process.stdout.write("\nPostorder traversal: ");
    postorder(root);
}

// Call the main method
main();

Output

Inorder traversal: D B E A F C G 
Preorder traversal: A B D E C F G 
Postorder traversal: D E B F G C A

Let’s see the difference between B-tree and Binary tree:

S.NO	B-tree	Binary tree
1.	In a B-tree, a node can have maximum ‘M'(‘M’ is the order of the tree) number of child nodes.	While in binary tree, a node can have maximum two child nodes or sub-trees.
2.	B-tree is called a sorted tree as its nodes are sorted in inorder traversal.	While binary tree is not a sorted tree. It can be sorted in inorder, preorder, or postorder traversal.
3.	B-tree has a height of log(M*N) (Where ‘M’ is the order of tree and N is the number of nodes).	While binary tree has a height of log₂(N) (Where N is the number of nodes).
4.	B-Tree is performed when the data is loaded into the disk.	Unlike B-tree, binary tree is performed when the data is loaded in the RAM(faster memory).
5.	B-tree is used in DBMS(code indexing, etc).	While binary tree is used in Huffman coding and Code optimization and many others.
6.	To insert the data or key in B-tree is more complicated than a binary tree.	While in binary tree, data insertion is not more complicated than B-tree.
7.	B-tree is a self-balancing tree. The height of the tree is automatically adjusted on each update.	A binary tree is not a self-balancing tree.

Tags:

#B-Tree #Binary Tree #Difference Between #DSA #Tree #Tree

Difference between B tree and B+ tree

Top MCQs on B and B+ Trees with Answers

Difference between Binary tree and B-tree

Contact Us