Binary Tree

Introduction

A Binary tree is a non-linear data structure where each node has at most two children, referred to as the left and right child. It organizes data hierarchically, making operations like searching, insertion, and deletion more efficient compared to linear structures.

Key Terms in Binary Trees

1. Root: The topmost node in the tree.

2. Parent: A node that has child nodes.

3. Child: A node derived from another node (parent).

4. Leaf: A node with no children.

5. Height: The number of edges on the longest path from the root to a leaf.

6. Depth: The number of edges from the root to a specific node.

Why Use Tree?

Hierarchical Data Representation

• Binary trees allow data to be structured in a hierarchical form, making relationships between elements clear.

Efficient Searching and Sorting

• In Binary Search Trees (BSTs), searching for an element has a time complexity of 𝑂(log𝑛) in a balanced tree, compared to 𝑂(𝑛) for unsorted linear structures.

• Trees make sorting and searching efficient when data needs frequent modifications.

Dynamic Data Handling

• Binary trees are flexible in size and can grow or shrink dynamically without the need for resizing or memory shifts (unlike arrays).

Support for Advanced Data Structures

Binary trees are building blocks for other data structures like:

• Heaps (used in priority queues).

• Huffman Trees (used in data compression).

• Tries (used in searching strings).

Visualization of Binary Tree

Representation of Binary Tree

Each node in a Binary Tree has three parts:

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

Coding Implementation

// implementationofbinarytree.cpp
#include<iostream>
using namespace std;
class tree{
public:
int data;
tree* left;
tree* right;
tree(int data){
    this->data=data;
    this->left=NULL;
    this->right=NULL;
}
};
int main(){
tree* root=new tree(1); // Create a root of Binary Tree
tree* leftChild=new tree(2); // Create a left child.
tree* rightChild=new tree(3);// Create a right child.
root->left=leftChild;// Link root to left child.
root->right=rightChild;// Link root to right child.
cout<<root->data<<endl; //1
cout<<root->left->data<<endl;//2
cout<<root->right->data<<endl;//3
}