## Code Avinya

Software Development Blogs

# Left Skewed binary tree

A binary tree is one of the famous data structures, and we already read about skewed binary trees in our previous blog. So, In this blog, we are discussing about the left-skewed binary tree in more depth.

So, let’s start this article with the basic definition.

## 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.

### About Us

Myself Bharath Choudhary, software developer at Oracle.

2021 NIT Warangal graduate.

### Categories

- About Companies (21)
- System Design (6)
- Uncategorized (36)

### Quick Contact

contact@codeavinya.com

Saturday – Sunday

10 AM – 5 PM

Follow Us :