Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes. Every node stores address of its children and the very first node’s address will be stored in a separate pointer called root.

The Generic trees are the N-ary trees which have the following properties: 

            1. Many children at every node.

            2. The number of nodes for each node is not known in advance.

Example: 
 

Generic Tree

To represent the above tree, we have to consider the worst case, that is the node with maximum children (in above example, 6 children) and allocate that many pointers for each node.
The node representation based on this method can be written as:
 

Disadvantages of the above representation are: 

1. Memory Wastage – All the pointers are not required in all the cases. Hence, there is lot of memory wastage.
2. Unknown number of children – The number of children for each node is not known in advance.

Simple Approach: 

For storing the address of children in a node we can use an array or linked list. But we will face some issues with both of them.

1. In Linked list, we can not randomly access any child’s address. So it will be expensive.
2. In array, we can randomly access the address of any child, but we can store only fixed number of children’s addresses in it.

Better Approach:

We can use Dynamic Arrays for storing the address of children. We can randomly access any child’s address and the size of the vector is also not fixed.

Efficient Approach:  

First child / Next sibling representation

 In the first child/next sibling representation, the steps taken are: 

At each node-link the children of the same parent(siblings) from left to right.

• Remove the links from parent to all children except the first child.

Since we have a link between children, we do not need extra links from parents to all the children. This representation allows us to traverse all the elements by starting at the first child of the parent.
 

FIRST CHILD/NEXT SIBLING REPRESENTATION

The node declaration for first child / next sibling representation can be written as: 
 

Advantages: 

• Memory efficient – No extra links are required, hence a lot of memory is saved.
• Treated as binary trees – Since we are able to convert any generic tree to binary representation, we can treat all generic trees with a first child/next sibling representation as binary trees. Instead of left and right pointers, we just use firstChild and nextSibling.
• Many algorithms can be expressed more easily because it is just a binary tree.
• Each node is of fixed size ,so no auxiliary array or vector is required.

Height of generic tree from parent array 
Generic tree – level order traversal

Binary Tree is a non-linear data structure where each node has at most two children. In this article, we will cover all the basics of Binary Tree, Operations on Binary Tree, its implementation, advantages, disadvantages which will help you solve all the problems based on Binary Tree.

What is Binary Tree?

Binary tree is a tree data structure(non-linear) in which each node can have at most two children which are referred to as the left child and the right child. 

The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves. A binary tree can be visualized as a hierarchical structure with the root at the top and the leaves at the bottom.

Representation of Binary Tree

Each node in a Binary Tree has three parts:

• Data
• Pointer to the left child
• Pointer to the right child

Below is the representation of a Node of Binary Tree in different languages:

// Use any below method to implement Nodes of tree

// Method 1: Using "struct" to make
// user-define data type
struct node {
    int data;
    struct node* left;
    struct node* right;
};

// Method 2: Using "class" to make
// user-define data type
class Node {
public:
    int data;
    Node* left;
    Node* right;
};

// Class containing left and right child
// of current node and key value
class Node {
    int key;
    Node left, right;

    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}

Types of Binary Tree

Binary Tree can be classified into multiples types based on multiple factors:

• On the basis of Number of Children
  • Full Binary Tree
  • Degenerate Binary Tree
  • Skewed Binary Trees
• On the basis of Completion of Levels
  • Complete Binary Tree
  • Perfect Binary Tree
  • Balanced Binary Tree
• On the basis of Node Values:
  • Binary Search Tree
  • AVL Tree
  • Red Black Tree
  • B Tree
  • B+ Tree
  • Segment Tree

Operations On Binary Tree

1. Insertion in Binary Tree

We can insert a node anywhere in a binary tree by inserting the node as the left or right child of any node or by making the node as root of the tree.

Algorithm to insert a node in a Binary Tree:

• Check if there is a node in the binary tree, which has missing left child. If such a node exists, then insert the new node as its left child.
• Check if there is a node in the binary tree, which has missing right child. If such a node exists, then insert the new node as its right child.
• If we don’t find any node with missing left or right child, then find the node which has both the children missing and insert the node as its left or right child.

2. Traversal of Binary Tree

Traversal of Binary Tree involves visiting all the nodes of the binary tree. Tree Traversal algorithms can be classified broadly into two categories:

• Depth-First Search (DFS) Algorithms
• Breadth-First Search (BFS) Algorithms

Depth-First Search (DFS) algorithms:

• Preorder Traversal (current-left-right): Visit the current node before visiting any nodes inside the left or right subtrees. Here, the traversal is root – left child – right child. It means that the root node is traversed first then its left child and finally the right child.
• Inorder Traversal (left-current-right): Visit the current node after visiting all nodes inside the left subtree but before visiting any node within the right subtree. Here, the traversal is left child – root – right child.  It means that the left child is traversed first then its root node and finally the right child.
• Postorder Traversal (left-right-current): Visit the current node after visiting all the nodes of the left and right subtrees.  Here, the traversal is left child – right child – root.  It means that the left child has traversed first then the right child and finally its root node.

Breadth-First Search (BFS) algorithms:

• Level Order Traversal:  Visit nodes level-by-level and left-to-right fashion at the same level. Here, the traversal is level-wise. It means that the most left child has traversed first and then the other children of the same level from left to right have traversed.

3. Deletion in Binary Tree

We can delete any node in the binary tree and rearrange the nodes after deletion to again form a valid binary tree.

Algorithm to delete a node in a Binary Tree:

• Starting at the root, find the deepest and rightmost node in the binary tree and the node which we want to delete. 
• Replace the deepest rightmost node’s data with the node to be deleted. 
• Then delete the deepest rightmost node.

4. Searching in Binary Tree

We can search for an element in the node by using any of the traversal techniques.

Algorithm to search a node in a Binary Tree:

• Start from the root node.
• Check if the current node’s value is equal to the target value.
• If the current node’s value is equal to the target value, then this node is the required node.
• Otherwise, if the node’s value is not equal to the target value, start the search in the left and right child.
• If we do not find any node whose value is equal to target, then the value is not present in the tree.

Auxiliary Operations On Binary Tree

• Finding the height of the tree
• Find level of a node in a Binary tree
• Finding the size of the entire tree

Implementation of Binary Tree

Below is the code for insertion, deletion and traversal of the binary tree:

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

// Node class to define the structure of the node
class Node {
    int data;
    Node left, right;
    // Parameterized Constructor
    Node(int val) {
        data = val;
        left = right = null;
    }
}

public class BinaryTree {
    // Function to insert nodes
    public static Node insert(Node root, int data) {
        // If tree is empty, new node becomes the root
        if (root == null) {
            root = new Node(data);
            return root;
        }
        // Queue to traverse the tree and find the position to
        // insert the node
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            Node temp = q.poll();
            // Insert node as the left child of the parent node
            if (temp.left == null) {
                temp.left = new Node(data);
                break;
            }
            // If the left child is not null push it to the
            // queue
            else
                q.offer(temp.left);
            // Insert node as the right child of parent node
            if (temp.right == null) {
                temp.right = new Node(data);
                break;
            }
            // If the right child is not null push it to the
            // queue
            else
                q.offer(temp.right);
        }
        return root;
    }

    /* function to delete the given deepest node
    (d_node) in binary tree */
    public static void deletDeepest(Node root, Node d_node) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        // Do level order traversal until last node
        Node temp;
        while (!q.isEmpty()) {
            temp = q.poll();
            if (temp == d_node) {
                temp = null;
                d_node = null;
                return;
            }
            if (temp.right != null) {
                if (temp.right == d_node) {
                    temp.right = null;
                    d_node = null;
                    return;
                } else
                    q.offer(temp.right);
            }
            if (temp.left != null) {
                if (temp.left == d_node) {
                    temp.left = null;
                    d_node = null;
                    return;
                } else
                    q.offer(temp.left);
            }
        }
    }

    /* function to delete element in binary tree */
    public static Node deletion(Node root, int key) {
        if (root == null)
            return null;
        if (root.left == null && root.right == null) {
            if (root.data == key)
                return null;
            else
                return root;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        Node temp = new Node(0);
        Node key_node = null;
        // Do level order traversal to find deepest
        // node(temp) and node to be deleted (key_node)
        while (!q.isEmpty()) {
            temp = q.poll();
            if (temp.data == key)
                key_node = temp;
            if (temp.left != null)
                q.offer(temp.left);
            if (temp.right != null)
                q.offer(temp.right);
        }
        if (key_node != null) {
            int x = temp.data;
            key_node.data = x;
            deletDeepest(root, temp);
        }
        return root;
    }

    // Inorder tree traversal (Left - Root - Right)
    public static void inorderTraversal(Node root) {
        if (root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.data + " ");
        inorderTraversal(root.right);
    }

    // Preorder tree traversal (Root - Left - Right)
    public static void preorderTraversal(Node root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    // Postorder tree traversal (Left - Right - Root)
    public static void postorderTraversal(Node root) {
        if (root == null)
            return;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.data + " ");
    }

    // Function for Level order tree traversal
    public static void levelorderTraversal(Node root) {
        if (root == null)
            return;

        // Queue for level order traversal
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            Node temp = q.poll();
            System.out.print(temp.data + " ");
            // Push left child in the queue
            if (temp.left != null)
                q.offer(temp.left);
            // Push right child in the queue
            if (temp.right != null)
                q.offer(temp.right);
        }
    }

    /* Driver function to check the above algorithm. */
    public static void main(String[] args) {
        Node root = null;
        // Insertion of nodes
        root = insert(root, 10);
        root = insert(root, 20);
        root = insert(root, 30);
        root = insert(root, 40);

        System.out.print("Preorder traversal: ");
        preorderTraversal(root);

        System.out.print("\nInorder traversal: ");
        inorderTraversal(root);

        System.out.print("\nPostorder traversal: ");
        postorderTraversal(root);

        System.out.print("\nLevel order traversal: ");
        levelorderTraversal(root);

        // Delete the node with data = 20
        root = deletion(root, 20);

        System.out.print("\nInorder traversal after deletion: ");
        inorderTraversal(root);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Node class to define the structure of the node
class Node {
public:
    int data;
    Node *left, *right;
    // Parameterized Constructor
    Node(int val)
    {
        data = val;
        left = right = NULL;
    }
};

// Function to insert nodes
Node* insert(Node* root, int data)
{
    // If tree is empty, new node becomes the root
    if (root == NULL) {
        root = new Node(data);
        return root;
    }
    // queue to traverse the tree and find the position to
    // insert the node
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        // Insert node as the left child of the parent node
        if (temp->left == NULL) {
            temp->left = new Node(data);
            break;
        }
        // If the left child is not null push it to the
        // queue
        else
            q.push(temp->left);
        // Insert node as the right child of parent node
        if (temp->right == NULL) {
            temp->right = new Node(data);
            break;
        }
        // If the right child is not null push it to the
        // queue
        else
            q.push(temp->right);
    }
    return root;
}

/* function to delete the given deepest node
(d_node) in binary tree */
void deletDeepest(Node* root, Node* d_node)
{
    queue<Node*> q;
    q.push(root);
    // Do level order traversal until last node
    Node* temp;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp == d_node) {
            temp = NULL;
            delete (d_node);
            return;
        }
        if (temp->right) {
            if (temp->right == d_node) {
                temp->right = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->right);
        }
        if (temp->left) {
            if (temp->left == d_node) {
                temp->left = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->left);
        }
    }
}

/* function to delete element in binary tree */
Node* deletion(Node* root, int key)
{
    if (!root)
        return NULL;
    if (root->left == NULL && root->right == NULL) {
        if (root->data == key)
            return NULL;
        else
            return root;
    }
    queue<Node*> q;
    q.push(root);
    Node* temp;
    Node* key_node = NULL;
    // Do level order traversal to find deepest
    // node(temp) and node to be deleted (key_node)
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp->data == key)
            key_node = temp;
        if (temp->left)
            q.push(temp->left);
        if (temp->right)
            q.push(temp->right);
    }
    if (key_node != NULL) {
        int x = temp->data;
        key_node->data = x;
        deletDeepest(root, temp);
    }
    return root;
}

// Inorder tree traversal (Left - Root - Right)
void inorderTraversal(Node* root)
{
    if (!root)
        return;
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

// Preorder tree traversal (Root - Left - Right)
void preorderTraversal(Node* root)
{
    if (!root)
        return;
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// Postorder tree traversal (Left - Right - Root)
void postorderTraversal(Node* root)
{
    if (root == NULL)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << " ";
}

// Function for Level order tree traversal
void levelorderTraversal(Node* root)
{
    if (root == NULL)
        return;

    // Queue for level order traversal
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        cout << temp->data << " ";
        // Push left child in the queue
        if (temp->left)
            q.push(temp->left);
        // Push right child in the queue
        if (temp->right)
            q.push(temp->right);
    }
}

/* Driver function to check the above algorithm. */
int main()
{
    Node* root = NULL;
    // Insertion of nodes
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);

    cout << "Preorder traversal: ";
    preorderTraversal(root);

    cout << "\nInorder traversal: ";
    inorderTraversal(root);

    cout << "\nPostorder traversal: ";
    postorderTraversal(root);

    cout << "\nLevel order traversal: ";
    levelorderTraversal(root);

    // Delete the node with data = 20
    root = deletion(root, 20);

    cout << "\nInorder traversal after deletion: ";
    inorderTraversal(root);
}

Preorder traversal: 10 20 40 30 
Inorder traversal: 40 20 10 30 
Postorder traversal: 40 20 30 10 
Level order traversal: 10 20 30 40 
Inorder traversal after deletion: 40 10 30 

Complexity Analysis of Binary Tree Operations

We can use Morris Traversal to traverse all the nodes of the binary tree in O(1) time.

Advantages of Binary Tree

• Efficient Search: Binary trees are efficient when searching for a specific element, as each node has at most two child nodes, allowing for binary search algorithms to be used.
• Memory Efficient: Binary trees require lesser memory as compared to other tree data structures, therefore they are memory-efficient.
• Binary trees are relatively easy to implement and understand as each node has at most two children, left child and right child.

Disadvantages of Binary Tree

• Limited structure: Binary trees are limited to two child nodes per node, which can limit their usefulness in certain applications. For example, if a tree requires more than two child nodes per node, a different tree structure may be more suitable.
• Unbalanced trees: Unbalanced binary trees, where one subtree is significantly larger than the other, can lead to inefficient search operations. This can occur if the tree is not properly balanced or if data is inserted in a non-random order.
• Space inefficiency: Binary trees can be space inefficient when compared to other data structures. This is because each node requires two child pointers, which can be a significant amount of memory overhead for large trees.
• Slow performance in worst-case scenarios: In the worst-case scenario, a binary tree can become degenerate or skewed, meaning that each node has only one child. In this case, search operations can degrade to O(n) time complexity, where n is the number of nodes in the tree.

Applications of Binary Tree

• Binary Tree can be used to represent hierarchical data.
• Huffman Coding trees are used in data compression algorithms.
• Priority Queue is another application of binary tree that is used for searching maximum or minimum in O(1) time complexity.
• Useful for indexing segmented at the database is useful in storing cache in the system,
• Binary trees can be used to implement decision trees, a type of machine learning algorithm used for classification and regression analysis.

Frequently Asked Questions on Binary Tree

1. What is a binary tree?

A binary tree is a non-linear data structure consisting of nodes, where each node has at most two children (left child and the right child).

2. What are the types of binary trees?

Binary trees can be classified into various types, including full binary trees, complete binary trees, perfect binary trees, balanced binary trees (such as AVL trees and Red-Black trees), and degenerate (or pathological) binary trees.

3. What is the height of a binary tree?

The height of a binary tree is the length of the longest path from the root node to a leaf node. It represents the number of edges in the longest path from the root node to a leaf node.

4. What is the depth of a node in a binary tree?

The depth of a node in a binary tree is the length of the path from the root node to that particular node. The depth of the root node is 0.

5. How do you perform tree traversal in a binary tree?

Tree traversal in a binary tree can be done in different ways: In-order traversal, Pre-order traversal, Post-order traversal, and Level-order traversal (also known as breadth-first traversal).

6. What is an Inorder traversal in Binary Tree?

In Inorder traversal, nodes are recursively visited in this order: left child, root, right child. This traversal results in nodes being visited in non-decreasing order in a binary search tree.

7. What is a Preorder traversal in Binary Tree?

In Preorder traversal, nodes are recursively visited in this order: root, left child, right child. This traversal results in root node being the first node to be visited.

8. What is a Postorder traversal in Binary Tree?

In Postorder traversal, nodes are recursively visited in this order: left child, right child and root. This traversal results in root node being the last node to be visited.

9. What is the difference between a Binary Tree and a Binary Search Tree?

A binary tree is a hierarchical data structure where each node has at most two children, whereas a binary search tree is a type of binary tree in which the left child of a node contains values less than the node’s value, and the right child contains values greater than the node’s value.

10. What is a balanced binary tree?

A balanced binary tree is a binary tree in which the height of the left and right subtrees of every node differ by at most one. Balanced trees help maintain efficient operations such as searching, insertion, and deletion with time complexities close to O(log n).

Conclusion:

Tree is a hierarchical data structure. Main uses of trees include maintaining hierarchical data, providing moderate access and insert/delete operations. Binary trees are special cases of tree where every node has at most two children.

Related Articles:

• Properties of Binary Tree
• Types of Binary Tree

We know a tree is a non-linear data structure. It has no limitation on the number of children. A binary tree has a limitation as any node of the tree has at most two children: a left and a right child.

What is a Complete Binary Tree?

A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

Complete Binary Tree

Some terminology of Complete Binary Tree:

• Root – Node in which no edge is coming from the parent. Example -node A
• Child – Node having some incoming edge is called child. Example – nodes B, F are the child of A and C respectively.
• Sibling – Nodes having the same parent are sibling. Example- D, E are siblings as they have the same parent B.
• Degree of a node – Number of children of a particular parent. Example- Degree of A is 2 and Degree of C is 1. Degree of D is 0.
• Internal/External nodes – Leaf nodes are external nodes and non leaf nodes are internal nodes.
• Level – Count nodes in a path to reach a destination node. Example- Level of node D is 2 as nodes A and B form the path.
• Height – Number of edges to reach the destination node, Root is at height 0. Example – Height of node E is 2 as it has two edges from the root.

Properties of Complete Binary Tree:

• A complete binary tree is said to be a proper binary tree where all leaves have the same depth.
• In a complete binary tree number of nodes at depth d is 2^d. 
• In a  complete binary tree with n nodes height of the tree is log(n+1).
• All the levels except the last level are completely full.

Perfect Binary Tree vs Complete Binary Tree:

A binary tree of height ‘h’ having the maximum number of nodes is a perfect binary tree. 
For a given height h, the maximum number of nodes is 2^h+1-1.

A complete binary tree of height h is a perfect binary tree up to height h-1, and in the last level element are stored in left to right order.

Example 1:

A Binary Tree

The height of the given binary tree is 2 and the maximum number of nodes in that tree is n= 2^h+1-1 =  2²⁺¹-1 =  2³-1 = 7.
Hence we can conclude it is a perfect binary tree.
Now for a complete binary tree, It is full up to height h-1 i.e.; 1, and the last level elements are stored in left to right order. Hence it is a complete Binary tree also. Here is the representation of elements when stored in an array

Element stored in an array level by level

In the array, all the elements are stored continuously.

Example 2:

A binary tree

Height of the given binary tree is 2 and the maximum number of nodes that should be there are 2^h+1 – 1 = 2²⁺¹ – 1 = 2³ – 1 = 7. 
But the number of nodes in the tree is 6. Hence it is not a perfect binary tree.
Now for a complete binary tree, It is full up to height h-1 i.e.; 1, and the last level element are stored in left to right order. Hence this is a complete binary tree. Store the element in an array and it will be like;

Element stored in an array level by level

Example 3:

A binary tree

The height of the binary tree is 2 and the maximum number of nodes that can be there is 7, but there are only 5 nodes hence it is not a perfect binary tree.
In case of a complete binary tree, we see that in the last level elements are not filled from left to right order. So it is not a complete binary tree.

Element stored in an array level by level

The elements in the array are not continuous.

Full Binary Tree vs Complete Binary tree:

For a full binary tree, every node has either 2 children or 0 children.

Example 1:

A binary tree

In the given binary tree there is no node having degree 1, either 2 or 0 children for every node, hence it is a full binary tree.

For a complete binary tree, elements are stored in level by level and not from the leftmost side in the last level. Hence this is not a complete binary tree. The array representation is:

Element stored in an array level by level

Example 2:

A binary Tree

In the given binary tree there is no node having degree 1. Every node has a degree of either 2 or 0. Hence it is a full binary tree.

For a complete binary tree, elements are stored in a level by level manner and filled from the leftmost side of the last level. Hence this a complete binary tree. Below is the array representation of the tree:

Element stored in an array level by level

Example 3:

A binary tree

In the given binary tree node B has degree 1 which violates the property of full binary tree hence it is not a full Binary tree

For a complete binary tree, elements are stored in level by level manner and filled from the leftmost side of the last level. Hence this is a complete binary tree. Array representation of the binary tree is:

Element stored in an array level by level

Example 4:
 

a binary tree

In the given binary tree node C has degree 1 which violates the property of a full binary tree hence it is not a full Binary tree

For a complete binary tree, elements are stored in level by level manner and filled from the leftmost side of the last level. Here node E violates the condition. Hence this is not a complete binary tree. 

Creation of Complete Binary Tree:

We know a complete binary tree is a tree in which except for the last level (say l)all the other level has (2l) nodes and the nodes are lined up from left to right side.
It can be represented using an array. If the parent is it index i so the left child is at 2i+1 and the right child is at 2i+2.

Complete binary tree and its array representation

Algorithm:

For the creation of a Complete Binary Tree, we require a queue data structure to keep track of the inserted nodes.

Step 1: Initialize the root with a new node when the tree is empty.

Step 2: If the tree is not empty then get the front element 

• If the front element does not have a left child then set the left child to a new node
• If the right child is not present set the right child as a new node

Step 3: If the node has both the children then pop it from the queue.

Step 4: Enqueue the new data.

Illustration:

Consider the below array:

1. The 1st element will the root (value at index = 0)

A is taken as root

2. The next element (at index = 1) will be left and third element (index = 2) will be right child of root

B as left child and D as right child

3. fourth (index = 3) and fifth element (index = 4) will be the left and right child of B node

E and F are left and right child of B

4. Next element (index = 5) will be left child of the node D

G is made left child of D node

This is how complete binary tree is created.

Implementation: For the implementation of building a Complete Binary Tree from level order traversal is given in this post.

Application of the Complete binary tree:

• Heap Sort
• Heap sort-based data structure

Check if a given binary tree is complete or not: Follow this post to check if the given binary tree is complete or not.

What is a Perfect Binary Tree?

A perfect binary tree is a special type of binary tree in which all the leaf nodes are at the same depth, and all non-leaf nodes have two children. In simple terms, this means that all leaf nodes are at the maximum depth of the tree, and the tree is completely filled with no gaps.

The maximum number of nodes in a perfect binary tree is given by the formula 2^(d+1) – 1, where d is the depth of the tree. This means that a perfect binary tree with a depth of n has 2^n leaf nodes and a total of 2^(n+1) – 1 nodes.

Perfect binary trees have a number of useful properties that make them useful in various applications. For example, they are often used in the implementation of heap data structures, as well as in the construction of threaded binary trees. They are also used in the implementation of algorithms such as heapsort and merge sort.

In other words, it can be said that each level of the tree is completely filled by the nodes.

Examples of Perfect Binary Tree: 

Example of a Perfect Binary Tree

A tree with only the root node is also a perfect binary tree.     

Example-2

The following tree is not a perfect binary tree because the last level of the tree is not completely filled.

Not a Perfect Binary Tree

Properties of a Perfect Binary Tree:

• Degree: The degree of a node of a tree is defined as the number of children of that node. All the internal nodes have a degree of 2. The leaf nodes of a perfect binary tree have a degree of 0.
• Number of leaf nodes: If the height of the perfect binary tree is h, then the number of leaf nodes will be 2^h because the last level is completely filled.
• Depth of a node: Average depth of a node in a perfect binary tree is Θ(ln(n)).
• Relation between leaf nodes and non-leaf nodes: No. of leaf nodes = No. of non-leaf nodes +1.
• Total number of nodes: A tree of height h has total nodes = 2^h+1 – 1. Each node of the tree is filled. So total number of nodes can be calculated as 2⁰ + 2¹ + . . . + 2^h = 2^h+1 – 1.
• Height of the tree: The height of a perfect binary tree with N number of nodes = log(N + 1) – 1 = Θ(ln(n)). This can be calculated using the relation shown while calculating the total number of nodes in a perfect binary tree.

Check whether a tree is a Perfect Binary Tree or not:

• Check the depth of the tree. A perfect binary tree is defined as a tree where all leaf nodes are at the same depth, and all non-leaf nodes have two children. To check whether a tree is a perfect binary tree, you can first calculate the depth of the tree.
• Check the number of nodes at each level: Once you have calculated the depth of the tree, you can then check the number of nodes at each level. In a perfect binary tree, the number of nodes at each level should be a power of 2 (e.g. 1, 2, 4, 8, etc.). If any level has a different number of nodes, the tree is not a perfect binary tree.

For more information about this refer to the article article: Check whether a given binary tree is perfect or not

Summary:

• All leaf nodes are at the same depth. In a perfect binary tree, all leaf nodes are at the maximum depth of the tree. This means that the tree is completely filled with no gaps.
• All non-leaf nodes have two children. In a perfect binary tree, all non-leaf nodes have exactly two children. This means that the tree has a regular structure, with all nodes having either two children or no children.
• The maximum number of nodes is given by a formula: The maximum number of nodes in a perfect binary tree is given by the formula 2^(d+1) – 1, where d is the depth of the tree.
• They have a symmetrical structure. This is because all non-leaf nodes have two children, perfect binary trees have a symmetrical structure.
• They can be represented using an array. Perfect binary trees can be represented using an array, where the left child of a node at index i is stored at index 2i+1 and the right child is stored at index 2i+2. This makes it easy to access the children of a node and to traverse the tree.

A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root-to-leaf path is the same and that there are no adjacent red nodes. Balanced Binary Search trees are performance-wise good as they provide O(log n) time for search, insert and delete. 

A balanced binary tree is a binary tree that follows the 3 conditions:

• The height of the left and right tree for any node does not differ by more than 1.
• The left subtree of that node is also balanced.
• The right subtree of that node is also balanced.

A single node is always balanced. It is also referred to as a height-balanced binary tree.

Example:

Balanced and Unbalanced Binary Tree

It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1. In the figure above, the root node having a value 0 is unbalanced with a depth of 2 units.

Application of Balanced Binary Tree:

• AVL Trees
• Red Black Tree
• Balanced Binary Search Tree

Advantages of Balanced Binary Tree:

• Non Destructive updates are supported by a Balanced Binary Tree with the same asymptotic effectiveness.
• Range queries and iteration in the right sequence are made feasible by the balanced binary tree.

Preorder traversal is defined as a type of tree traversal that follows the Root-Left-Right policy where:

• The root node of the subtree is visited first.
• Then the left subtree  is traversed.
• At last, the right subtree is traversed.

Preorder traversal

Algorithm for Preorder Traversal of Binary Tree

The algorithm for preorder traversal is shown as follows:

Preorder(root):

1. Follow step 2 to 4 until root != NULL
2. Write root -> data
3. Preorder (root -> left)
4. Preorder (root -> right)
5. End loop

How does Preorder Traversal of Binary Tree work?

Consider the following tree:

Example of Binary Tree

If we perform a preorder traversal in this binary tree, then the traversal will be as follows:

Step 1: At first the root will be visited, i.e. node 1.

Node 1 is visited

Step 2: After this, traverse in the left subtree. Now the root of the left subtree is visited i.e., node 2 is visited.

Node 2 is visited

Step 3: Again the left subtree of node 2 is traversed and the root of that subtree i.e., node 4 is visited.

Node 4 is visited

Step 4: There is no subtree of 4 and the left subtree of node 2 is visited. So now the right subtree of node 2 will be traversed and the root of that subtree i.e., node 5 will be visited.

Node 5 is visited

Step 5: The left subtree of node 1 is visited. So now the right subtree of node 1 will be traversed and the root node i.e., node 3 is visited.

Node 3 is visited

Step 6: Node 3 has no left subtree. So the right subtree will be traversed and the root of the subtree i.e., node 6 will be visited. After that there is no node that is not yet traversed. So the traversal ends.

The complete tree is visited

So the order of traversal of nodes is 1 -> 2 -> 4 -> 5 -> 3 -> 6.

Program to Implement Preorder Traversal of Binary Tree

Below is the code implementation of the preorder traversal:

// C++ program for preorder traversals

#include <bits/stdc++.h>
using namespace std;

// Structure of a Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
    Node(int v)
    {
        data = v;
        left = right = NULL;
    }
};

// Function to print preorder traversal
void printPreorder(struct Node* node)
{
    if (node == NULL)
        return;

    // Deal with the node
    cout << node->data << " ";

    // Recur on left subtree
    printPreorder(node->left);

    // Recur on right subtree
    printPreorder(node->right);
}

// Driver code
int main()
{
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);

    // Function call
    cout << "Preorder traversal of binary tree is: \n";
    printPreorder(root);

    return 0;
}

// Java program for preorder traversals

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    // Function to print preorder traversal
    void printPreorder(Node node) {
        if (node == null)
            return;

        // Deal with the node
        System.out.print(node.data + " ");

        // Recur on left subtree
        printPreorder(node.left);

        // Recur on right subtree
        printPreorder(node.right);
    }

    // Driver code
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // Constructing the binary tree
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.right = new Node(6);

        // Function call
        System.out.println("Preorder traversal of binary tree is: ");
        tree.printPreorder(tree.root);
    }
}

Preorder traversal of binary tree is: 
1 2 4 5 3 6 

Explanation:

How preorder traversal works

Complexity Analysis:

Time Complexity: O(N) where N is the total number of nodes. Because it traverses all the nodes at least once.
Auxiliary Space: 

• O(1) if no recursion stack space is considered. 
• Otherwise, O(h) where h is the height of the tree
• In the worst case, h can be the same as N (when the tree is a skewed tree)
• In the best case, h can be the same as logN (when the tree is a complete tree)

Use cases of Preorder Traversal:

Some use cases of preorder traversal are:

• This is often used for creating a copy of a tree.
• It is also useful to get the prefix expression from an expression tree.

Related Articles:

• Types of Tree Traversal
• Iterative preorder traversal
• Check if given array can represent preorder traversal of BST
• Preorder from inorder and postorder traversals
• Find nth node in preorder traversal of a binary tree
• Preorder traversal of an N-ary tree

Inorder traversal is defined as a type of tree traversal technique which follows the Left-Root-Right pattern, such that:

• The left subtree is traversed first
• Then the root node for that subtree is traversed
• Finally, the right subtree is traversed

Inorder traversal

Algorithm for Inorder Traversal of Binary Tree

The algorithm for inorder traversal is shown as follows:

Inorder(root):

1. Follow step 2 to 4 until root != NULL
2. Inorder (root -> left)
3. Write root -> data
4. Inorder (root -> right)
5. End loop

How does Inorder Traversal of Binary Tree work?

Consider the following tree:

Example of Binary Tree

If we perform an inorder traversal in this binary tree, then the traversal will be as follows:

Step 1: The traversal will go from 1 to its left subtree i.e., 2, then from 2 to its left subtree root, i.e., 4. Now 4 has no left subtree, so it will be visited. It also does not have any right subtree. So no more traversal from 4

Node 4 is visited

Step 2: As the left subtree of 2 is visited completely, now it read data of node 2 before moving to its right subtree.

Node 2 is visited

Step 3: Now the right subtree of 2 will be traversed i.e., move to node 5. For node 5 there is no left subtree, so it gets visited and after that, the traversal comes back because there is no right subtree of node 5.

Node 5 is visited

Step 4: As the left subtree of node 1 is, the root itself, i.e., node 1 will be visited.

Node 1 is visited

Step 5: Left subtree of node 1 and the node itself is visited. So now the right subtree of 1 will be traversed i.e., move to node 3. As node 3 has no left subtree so it gets visited.

Node 3 is visited

Step 6: The left subtree of node 3 and the node itself is visited. So traverse to the right subtree and visit node 6. Now the traversal ends as all the nodes are traversed.

The complete tree is traversed

So the order of traversal of nodes is 4 -> 2 -> 5 -> 1 -> 3 -> 6.

Program to implement Inorder Traversal of Binary Tree:

Below is the code implementation of the inorder traversal:

Inorder traversal of binary tree is: 
4 2 5 1 3 6 

Explanation:

How inorder traversal works

Complexity Analysis:

Time Complexity: O(N) where N is the total number of nodes. Because it traverses all the nodes at least once.
Auxiliary Space: O(1) if no recursion stack space is considered. Otherwise, O(h) where h is the height of the tree

• In the worst case, h can be the same as N (when the tree is a skewed tree)
• In the best case, h can be the same as logN (when the tree is a complete tree)

Use cases of Inorder Traversal:

In the case of BST (Binary Search Tree), if any time there is a need to get the nodes in non-decreasing order, the best way is to implement an inorder traversal.

Related Articles:

• Types of Tree Traversals
• Iterative inorder traversal
• Construct binary tree from preorder and inorder traversal
• Morris traversal for inorder traversal of tree
• Inorder traversal without recursion

Postorder traversal is defined as a type of tree traversal which follows the Left-Right-Root policy such that for each node:

• The left subtree is traversed first
• Then the right subtree is traversed
• Finally, the root node of the subtree is traversed

Postorder traversal

Algorithm for Postorder Traversal of Binary Tree:

The algorithm for postorder traversal is shown as follows:

Postorder(root):

1. Follow step 2 to 4 until root != NULL
2. Postorder (root -> left)
3. Postorder (root -> right)
4. Write root -> data
5. End loop

How does Postorder Traversal of Binary Tree Work?

Consider the following tree:

Example of Binary Tree

If we perform a postorder traversal in this binary tree, then the traversal will be as follows:

Step 1: The traversal will go from 1 to its left subtree i.e., 2, then from 2 to its left subtree root, i.e., 4. Now 4 has no subtree, so it will be visited.

Node 4 is visited

Step 2: As the left subtree of 2 is visited completely, now it will traverse the right subtree of 2 i.e., it will move to 5. As there is no subtree of 5, it will be visited.

Node 5 is visited

Step 3: Now both the left and right subtrees of node 2 are visited. So now visit node 2 itself.

Node 2 is visited

Step 4: As the left subtree of node 1 is traversed, it will now move to the right subtree root, i.e., 3. Node 3 does not have any left subtree, so it will traverse the right subtree i.e., 6. Node 6 has no subtree and so it is visited.

Node 6 is visited

Step 5: All the subtrees of node 3 are traversed. So now node 3 is visited.

Node 3 is visited

Step 6: As all the subtrees of node 1 are traversed, now it is time for node 1 to be visited and the traversal ends after that as the whole tree is traversed.

The complete tree is visited

So the order of traversal of nodes is 4 -> 5 -> 2 -> 6 -> 3 -> 1.

Program to implement Postorder Traversal of Binary Tree

Below is the code implementation of the postorder traversal:

Postorder traversal of binary tree is: 
4 5 2 6 3 1 

Explanation:

How postorder traversal works

Complexity Analysis:

Time Complexity: O(N) where N is the total number of nodes. Because it traverses all the nodes at least once.
Auxiliary Space: O(1) if no recursion stack space is considered. Otherwise, O(h) where h is the height of the tree

• In the worst case, h can be the same as N (when the tree is a skewed tree)
• In the best case, h can be the same as logN (when the tree is a complete tree)

Use cases of Postorder Traversal:

Some use cases of postorder traversal are:

• This is used for tree deletion.
• It is also useful to get the postfix expression from an expression tree.

Related articles:

• Types of Tree traversals
• Iterative Postorder traversal (using two stacks)
• Iterative Postorder traversal (using one stack)
• Postorder of Binary Tree without recursion and without stack
• Find Postorder traversal of BST from preorder traversal
• Morris traversal for Postorder
• Print postorder traversal from preoreder and inorder traversal

Level Order Traversal technique is defined as a method to traverse a Tree such that all nodes present in the same level are traversed completely before traversing the next level.

Example:

Input:

Output:
1
2 3
4 5

How does Level Order Traversal work?

The main idea of level order traversal is to traverse all the nodes of a lower level before moving to any of the nodes of a higher level. This can be done in any of the following ways: 

• the naive one (finding the height of the tree and traversing each level and printing the nodes of that level)
• efficiently using a queue.

Level Order Traversal (Naive approach):

Find height of tree. Then for each level, run a recursive function by maintaining current height. Whenever the level of a node matches, print that node.

Below is the implementation of the above approach:

// Recursive CPP program for level
// order traversal of Binary Tree
#include <bits/stdc++.h>
using namespace std;

// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class node {
public:
    int data;
    node *left, *right;
};

// Function prototypes
void printCurrentLevel(node* root, int level);
int height(node* node);
node* newNode(int data);

// Function to print level order traversal a tree
void printLevelOrder(node* root)
{
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++)
        printCurrentLevel(root, i);
}

// Print nodes at a current level
void printCurrentLevel(node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        printCurrentLevel(root->left, level - 1);
        printCurrentLevel(root->right, level - 1);
    }
}

// Compute the "height" of a tree -- the number of
// nodes along the longest path from the root node
// down to the farthest leaf node.
int height(node* node)
{
    if (node == NULL)
        return 0;
    else {
        
        // Compute the height of each subtree
        int lheight = height(node->left);
        int rheight = height(node->right);

        // Use the larger one
        if (lheight > rheight) {
            return (lheight + 1);
        }
        else {
            return (rheight + 1);
        }
    }
}

// Helper function that allocates
// a new node with the given data and
// NULL left and right pointers.
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return (Node);
}

// Driver code
int main()
{
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    cout << "Level Order traversal of binary tree is \n";
    printLevelOrder(root);

    return 0;
}

// This code is contributed by rathbhupendra