Basic Operations on Binary Tree in C

The following are the basics operations that can performed on a binary tree:

• Insertion
• Deletion
• Search
• Traversing (Pre-order, Post-order and In-order)

Here, we will learn about three basic operations that can be performed on a binary: insertion, deletion, and searching.

1. Insertion in Binary Tree

In a binary tree a new node can be inserted anywhere as a right child or left child of a node. To insert a node in a binary tree, follow the below approach:

Approach:

• Start iterating using level order traversal in a binary tree.
• If a node whose left child is missing is found then insert the given new node as the left child of that node.
• Else if a node whose right child is missing is found then insert the given node as the right child of that node.
• Else a node whose both right child and left child are missing is found then insert the new node as the left or right child (any position) of that node.

2. Deletion in Binary Tree

In a binary tree we can delete a node from anywhere and then again rearrange it to maintain the property of binary tree and the leaf nodes can be deleted without performing any replacement and shifting of nodes. To delete a node from a binary tree, follow the below approach:

Approach:

• Start traversing from the root node of the tree.
• Find the node that you want to delete and the node at the deepest right.
• Replace the target node (node to be deleted ) with the deepest rightmost node.
• Finally, delete the deepest rightmost node (as it contains the node to be deleted now).

3. Searching in Binary Tree

In a binary tree we can search a node by traversing and comparing each node with target node (node to be searched). To search for a given node in a binary tree follow the below approach:

Approach:

• Start traversing from the root node of the tree.
• Compare the target node (node to be searched) with each node’s value.
  • If the current node’s value is equal to target node, then target node is found.
  • else if, the current node’s value is not equal to target node, again start searching the left and right child by traversing.
  • else, you reach the end of the tree and do no find any node’s value equal to target value, then the target node is not present in the tree.

A binary tree is a non-linear hierarchical data structure in which each node has at most two children known as the left child and the right child. It can be visualized as a hierarchical structure where the topmost node is called the root node and the nodes at the bottom are called leaf nodes or leaves.

In this article, we will learn the basics of binary trees, types of binary trees, basic operations that can be performed on binary trees as well as applications, advantages, and disadvantages of binary trees in C.