Binary Trees in Data Structures - Types, Implementation, Applications

Binary Trees in Data Structures: An Overview

A binary tree is a type of tree data structure. In this DSA tutorial, we will see the binary tree in detail learning about its features, working, types, implementation, etc. To further enhance your understanding and application of binary tree concepts, consider enrolling in the best Data Structures and Algorithms Certification, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Binary Tree in Data Structures?

A binary tree is the specialized version of the General tree. In this, according to the name, binary, each parent node can have at most two nodes or two children i.e. left and right child.

Binary Tree Representation in Data Structures

A Binary tree is represented by a pointer to the topmost node known as the root node. If the tree is empty, the value of the root is NULL. Each node of a Binary Tree contains the following three elements:

1. Data
2. Pointer to the left child
3. Pointer to the right child

Binary Tree Terminologies in Data Structures

1. Node: In a binary tree, a node refers to a data element stored in the tree. They contain the address of the left and right child.
2. Root: In a binary tree, the root is the topmost node of the tree. It is the starting point of the tree from which all other nodes branch out. A tree can have at most one root node.
3. Parent Node: A node (except the root) that has a succeeding node is known as a parent node.
4. Child Node: A node that has a preceding node is known as a child node. A node can be both parent and child depending on the node that is in context.
5. Leaf Node: A leaf node in a binary tree is a node that does not have any children i.e. terminal node in the tree.
6. Internal Node: In a binary tree, an internal node is a node that has at least one child.
7. Depth of a Tree: The depth of a tree in a binary tree refers to the length of the longest path from the root node to any leaf node in the tree.
8. Height of a Tree: The number of edges from the deepest node in the tree to the root node.

Read More - Data Structure Interview Questions for Freshers

Types of Binary Trees in Data Structures

1. Full/ proper/ strict Binary Tree

A full binary tree, also known as a proper binary tree or a strictly binary tree, is a type of binary tree in which every node has either zero or two children. Additionally, all leaf nodes are at the same level.

Properties of a Full Binary Tree

• The number of internal nodes is (n-1)/2 if n is the number of total nodes.
• The number of leaf nodes is equal to the number of internal nodes plus 1.
• The maximum number of nodes is the same as the number of nodes in the binary tree with height h, i.e., 2h+1 -1.
• The minimum number of nodes in the full binary tree with height h is 2*h-1.
• The minimum height of the full binary tree is log2(n+1) - 1.

2. Complete Binary Tree

A complete binary tree is a full binary tree but with some major differences

• Every level must be filled completely except the last level which may or may not be completely filled.
• All the leaf elements must lean towards the left.
• The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.

Properties of a Complete Binary Tree

• The maximum number of nodes in a complete binary tree is 2h+1 - 1.
• The minimum number of nodes in a complete binary tree is 2h.
• The minimum height of a complete binary tree is log2(n+1) - 1.

3. Perfect Binary Tree

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.

Properties of a Perfect Binary Tree

• The number of nodes in a perfect binary tree can be calculated using the formula 2^h - 1, where h is the height or depth of the tree.
• The height of a perfect binary tree can be calculated using the formula log2(n + 1) - 1, where n is the number of nodes in the tree.
• The root node of a perfect binary tree is always at level 0.
• The number of nodes in the last level of a perfect binary tree is equal to 2^(h-1), where h is the height of the tree.
• The maximum number of nodes at any level of a perfect binary tree is 2^k, where k is the level number.
• The minimum height of a perfect binary tree with n nodes is floor(log2(n)).

4. Degenerate Binary Tree

A degenerate binary tree, also known as a pathological tree, is a special type of binary tree where each parent node has only one child node. In other words, it is a tree in which all the internal nodes have a degree of 1, and only the leaf nodes have a degree of 0.

Degenerate binary trees can also be classified into two types

1. Left-skewed: A degenerate binary tree in which all the nodes lean towards the left side of the tree.

   

2. Right-skewed: A degenerate binary tree in which all the nodes lean towards the right side of the tree.

   

5. Balanced Binary Tree

A balanced binary tree is a type of binary tree in which the difference in height between the left and right subtrees of any node is at most one.

Some Special Types of Binary Trees

Based on node values, the Binary Tree can be classified into the following special types:

1. Binary Search Tree: In this, the value of the left node must be smaller than the parent node, and the value of the right node must be greater than the parent node.

   We will learn more on this topic in Binary Search Trees in Data Structures

2. AVL Tree: It is a self-balancing binary search tree where the difference between the heights of left and right subtrees for any node is not more than one.

   We will learn more on this topic in AVL Tree in Data Structures

3. Red Black Tree: It is a type of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black). These colors ensure that the tree remains balanced during insertions and deletions.

   

4. B Tree: It has a fixed maximum degree (or order), which determines the maximum number of child nodes that a parent node can have. Each node in a B-tree can have multiple child nodes and multiple keys, which are used to index and locate data items.
5. B+ Tree: It is a type of B-tree and also has a fixed maximum degree. in a B+ tree, all data items are stored in the leaf nodes, while the internal nodes only contain keys for indexing and locating the data items.
6. Segment Tree: It is a tree data structure used for storing information about intervals, or segments.

   We will learn more on this topic in Segment Tree in Data Structures

How to declare/create a Binary Tree in Data Structures?

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

Implementation of a Binary Tree in Different Programming Languages

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

    # Traverse preorder
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # Traverse inorder
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if self.right:
            self.right.traverseInOrder()

    # Traverse postorder
    def traversePostOrder(self):
        if self.left:
            self.left.traversePostOrder()
        if self.right:
            self.right.traversePostOrder()
        print(self.val, end=' ')


root = Node(5)

root.left = Node(6)
root.right = Node(7)

root.left.left = Node(8)

print("Preorder Traversal: ", end="")
root.traversePreOrder()
print("\nInorder Traversal: ", end="")
root.traverseInOrder()
print("\nPostorder Traversal: ", end="")
root.traversePostOrder()
    

// Node creation
class Node {
  int key;
  Node left, right;

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

class BinaryTree {
  Node root;

  BinaryTree(int key) {
  root = new Node(key);
  }

  BinaryTree() {
  root = null;
  }

  // Traverse Inorder
  public void traverseInOrder(Node node) {
  if (node != null) {
    traverseInOrder(node.left);
    System.out.print(" " + node.key);
    traverseInOrder(node.right);
  }
  }

  // Traverse Postorder
  public void traversePostOrder(Node node) {
  if (node != null) {
    traversePostOrder(node.left);
    traversePostOrder(node.right);
    System.out.print(" " + node.key);
  }
  }

  // Traverse Preorder
  public void traversePreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.key);
    traversePreOrder(node.left);
    traversePreOrder(node.right);
  }
  }

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

  tree.root = new Node(5);
  tree.root.left = new Node(6);
  tree.root.right = new Node(7);
  tree.root.left.left = new Node(8);

  System.out.print("Preorder Traversal: ");
  tree.traversePreOrder(tree.root);
  System.out.print("\nInorder Traversal: ");
  tree.traverseInOrder(tree.root);
  System.out.print("\nPostorder Traversal: ");
  tree.traversePostOrder(tree.root);
  }
}
    

#include <stdlib.h>
#include <iostream>
using namespace std;

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

// New node creation
struct node *newNode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;
  node->right = NULL;
  return (node);
}

// Traverse Preorder
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout << " " << temp->data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// Traverse Inorder
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout << " " << temp->data;
    traverseInOrder(temp->right);
  }
}

// Traverse Postorder
void traversePostOrder(struct node *temp) {
  if (temp != NULL) {
    traversePostOrder(temp->left);
    traversePostOrder(temp->right);
    cout << " " << temp->data;
  }
}

int main() {
  struct node *root = newNode(5);
  root->left = newNode(6);
  root->right = newNode(7);
  root->left->left = newNode(8);

  cout << "preorder traversal: ";
  traversePreOrder(root);
  cout << "\nInorder traversal: ";
  traverseInOrder(root);
  cout << "\nPostorder traversal: ";
  traversePostOrder(root);
}
    

Output

Preorder traversal:  5 6 8 7
Inorder traversal:  8 6 5 7
Postorder traversal:  8 6 7 5

Complexity Analysis of Binary Tree Operations

1. Time Complexity

   OPERATION	BEST CASE	AVERAGE CASE	WORST CASE
   Insertion	O(logN)	O(N^0.5)	O(N)
   Search	O(1)	O(N^0.5)	O(N)
   Deletion	O(logN)	O(N^0.5)	O(N)

2. Space Complexity: The space complexity of the Binary Tree for all operations is O(N).

Applications of Binary Trees

1. Search algorithms: Binary search algorithms use the structure of binary trees to efficiently search for a specific element.
2. Sorting algorithms: Binary trees can be used to implement efficient sorting algorithms, such as tree sort and heap sort.
3. Database systems: Binary trees can be used to store data in a database system, with each node representing a record. This allows for efficient search operations and enables the database system to handle large amounts of data.
4. File systems: Binary trees can be used to implement file systems, where each node represents a directory or file.
5. Compression algorithms: Binary trees can be used to implement Huffman coding, a compression algorithm that assigns variable-length codes to characters based on their frequency of occurrence in the input data.
6. Decision trees: Binary trees can be used to implement decision trees.
7. Game AI: Binary trees can be used to implement game AI, where each node represents a possible move in the game. The AI algorithm can search the tree to find the best possible move.

Advantages of Binary Trees

1. Efficient searching: Binary trees are particularly efficient when searching for a specific element, as each node has at most two child nodes, allowing for binary search algorithms to be used.
2. Ordered traversal: The structure of binary trees enables them to be traversed in a specific order, such as in-order traversal, pre-order traversal, and post-order traversal.
3. Memory efficiency: Compared to other tree structures, binary trees are relatively memory-efficient because they only require two child pointers per node.
4. Easy to implement: Binary trees are relatively easy to implement and understand, making them a popular choice for a wide range of applications.

Disadvantages of Binary Trees

1. Limited structure: Binary trees are limited to two child nodes per node, which can limit their usefulness in certain applications.
2. Unbalanced trees: Unbalanced binary trees, 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.
3. 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.
4. Slow performance in worst-case scenarios: In the worst-case scenario, a binary tree can become degenerate, meaning that each node has only one child. In this case, search operations can degrade to O(n) time complexity.
5. Complex balancing algorithms: To ensure that binary trees remain balanced, various balancing algorithms can be used, such as AVL trees and red-black trees. These algorithms can be complex to implement and require additional overhead, making them less suitable for some applications.

Summary

The tutorial covers all the aspects from definition to advantages and disadvantages of binary trees in data structures. The topic is very important to understand other topics like binary search trees, AVL trees, segment trees, etc. Therefore refer to the tutorial until you get thorough with every detail of binary tree. To test your knowledge of binary trees, enroll in our DSA Training.