Home » Binary Tree in C++

C++ programmingData structures

Binary Tree in C++

Mayank Mandhana

June 1, 2021

0

SaveSavedRemoved 1

Binary Tree

A binary tree is a fundamental tree data structure in which every parent node can have at most two children. The binary tree is a helpful data structure for swiftly storing data and quickly retrieving stored data. A binary tree is made of parent nodes or leaves, each holding data, and links to up to two other child nodes (leaves). The connection between the leaves linked to and the linking leaf, also known as the parent node, makes the binary tree such an effective data structure. The leaf on the left has a minor key value, and it is the leaf on the right that has an equal or larger key value.

Trees: Unlike Arrays, Stack, Queues, Linked Lists, are linear data structures, whereas trees are hierarchical data structures.
Tree Vocabulary: The highest node is called the root of the tree. The component elements that are directly under an element are called its children nodes. The element immediately above something is called its parent.

Types of Binary Tree

Full Binary Tree

A full Binary tree is a special type of binary tree in which every node other than the leaves has two children.

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.

Complete Binary Tree

A complete binary tree is like a full binary tree, but with two major differences,

1. Every level needs to be fully filled.
2. All the leaf components must lean towards the left.
3. The last leaf component might not have a right sibling i.e. a complete binary tree does not have to be a full binary tree.

Skewed Binary Tree

It is a type of tree that is a degenerate tree in which the tree is either dominated by the left nodes or the right nodes. There are two types of skewed binary trees: left-skewed binary tree and right-skewed binary tree.

Balanced Binary Tree

It is a type of binary tree in which the difference among the height of the left and the right subtree for every node is either 0 or 1.

SYNTAX:

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

Binary Tree Applications

• In router algorithms
• For easy and quick access to data
• To implement a heap data structure
• Syntax tree

Why Trees? 
1. Trees are useful for storing information that typically forms a hierarchy.
2. Trees provide quicker search than Linked List and Arrays. 
3. Trees provide quicker insertion/deletion operation.
4.Trees don’t have an upper limit on the number of nodes.

Main applications of trees include: 
1. Used to Manage hierarchical data. 
2. Makes information easy to search for.
3. Used to Handle sorted lists of data. 
4. Used for compositing digital concepts for visual effects. 
5. Router algorithms.
6. Used for multi-stage decision-making.

Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node comprises only nodes with keys more inferior than the node’s key.
• The right subtree of a node comprises only nodes with keys more prominent than the node’s key.
• The left and right subtree each need to be a binary search tree. 
• No duplicate nodes allowed.