Left Skewed binary tree

Understanding Left-Skewed Binary Trees

The left-skewed binary tree is a type of skewed binary tree. In this type, each node has at most one child(Node >=1), which is positioned to the left side only, and the right child of every parent node should be null. And there should be no child node for the leaf node.

So, we can say that the left-skewed tree is an unbalanced binary tree titled toward the left side only.

Note: The height of this tree is directly proportional to the number of nodes the left-skewed tree contains. The more nodes it has, the taller the tree becomes.

Code:

#include <iostream>

// This is a basic structure to initialize a node in the binary tree
struct Node {// this represents a node
    int data;  //represents the data stored in the node. 
    Node* left; /*This member is a pointer to the left child of the current node. 
                 It points to another Node structure that represents the left child node. 
                 If there is no left child, the pointer is set to nullptr */
    Node* right;
};

// Function to create a new node with the given data
Node* createANewNode(int data) {
    Node* newNode = new Node(); //This line dynamically allocates memory for a new Node 
    newNode->data = data; /*This line sets the data member of the newNode
                          to the value passed as the data parameter 
                          to the createNode function.*/
    newNode->left = newNode->right = nullptr; //no left and right child
    return newNode;
}

// Function to insert a node into the left-skewed binary tree
Node* insertNode(Node* root, int data) {
    // If the tree is empty, create a new node and set it as the root
    if (root == nullptr) {  //if tree is empty it will creates a new node
        root = createANewNode(data);
    }
    // If the tree is not empty, insert the new node as the left child of the root
    else {
        root->left = insertNode(root->left, data);
    }
    return root;
}

// Function to traverse and print the left-skewed binary tree (inorder traversal)
void inorderTraversal(Node* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    // Creating a left-skewed binary tree
    Node* root = nullptr;
    root = insertNode(root, 4);
    insertNode(root, 3);
    insertNode(root, 2);
    insertNode(root, 1);
   
    
    // Printing the left-skewed binary tree
    std::cout << "Left-skewed binary tree: ";
    inorderTraversal(root);
    
    return 0;
}

Properties of Left-Skewed Binary Trees:

1. Imbalance

The absence of the right child causes this tree to become completely imbalanced. And because of this property, it can affect the overall tree functioning and may result in inefficient operations as compared to other balanced trees like AVL trees or Red-Black Trees.

2. Height

The height of a left-skewed tree is another problem because as the tree size increases, as node towards the left side increases. And because of this, it’s taking longer time to do search and transverse operations.

Applications of Left-Skewed Binary Trees:

1. To solve expression problems

This tree is commonly utilized to represent mathematical expressions, making it easy to represent an expression such as “((7 + 4) * 9)”.

2. Used in Priority Queues

Priority queues data structure can be implemented using left-skewed binary trees.

3. Huffman Coding

Huffman coding, a popular compression algorithm, also utilizes left-skewed binary trees.

Benefits :

1. Insertion Operation

Inserting a new node into a Left Skewed Tree is a very efficient operation. Since this tree will always be skewed towards the left side only, the new node can be added easily by maintaining the skewness property of this tree without facing any complex sorting.

2. Merging Feature

Merging two Left Skewed Trees is very easy. We just have to attach the root of one tree as the left child of the root of the other tree by maintaining the skewness property of both trees.

Difference between the Left Skewed Binary Tree vs. Balanced Binary Tree

In a balanced binary tree, the heights of the left and right subtrees are equal. On the other hand, the Left Skewed Binary Tree is skewed toward the left side only, and later it degenerates into a linked list only if the nodes are inserted in sorted order. 

However, in such scenarios where insertion and merging operations are more frequent than search or traversal operations, we can go for Left Skewed Binary Tree.

Difference between Left Skewed Binary Tree vs. Linked List

A Left Skewed Tree may resemble a linked list when all the nodes are inserted in a sorted manner. However, unlike a linked list, a Left Skewed Binary Tree still provides efficient merge and traverse operations. 

So, we can conclude this blog by saying that the Left Skewed Binary Tree is a unique data structure that offers efficiency and simplicity in certain scenarios.