## Code Avinya

Software Development Blogs

**Skewed Binary Tree**

Binary trees are an essential data structure in organizing as well as managing data efficiently. And Skewed binary tree is one of the types of binary tree used in database indexing, file system, and many more real-life scenarios like these.

So, to get a deep understanding of skewed binary trees, explore their structure, characteristics, practical applications, and many more topics like this, read this blog.

So, here we go:

## Skewed Binary Tree Definition: Understand the Concept and Characteristics

The skewed Binary tree is one of the famous types of Binary Tree Data Structure. And the main difference between the binary and skewed binary trees is that a binary tree can have at most two child nodes for each parent node (Node >= 2) whereas a Skewed binary tree can have only one child node (Node = 1) or no child at all (Node = 0).

Also, a skewed binary tree is a special binary tree because all the node’s branches are either on the left or right side.

## Properties:

- All the Parent nodes should have only one child node.
- Every parent’s child node should be in the same direction, whether all the child nodes should be in the right or left direction.
- The leaf node should not have a child node.

## Type of Skewed Binary Tree:

#### There are two types of skewed binary trees:

**Left-Skewed Binary Tree**: In a left-skewed binary tree, each parent node has only a left child node or has no child at all. Also, there should not be any right child node. So, we can say that, this tree extends primarily towards the left side only.

**Note:** In Left Skewed Tree, the root node should be greater than every child node (5<-4<-3<- 2<- 1)

2. **Right-Skewed Binary Tree**: Unlike the left-skewed binary tree, the right-skewed binary tree only extends towards the right side, and the parent node can have only the right child node or null.

N**ote:** In Right Skewed Tree, the root node should be lesser than every child node. (1->2->3->4->5)

## Program:

#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); } /* for right skewed binary tree: else { root->right = insertNode(root->right, 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; }

## Summary of the above program:

- The program in C++ enables the insertion of nodes into a left-skewed binary tree, using a Node structure with an integer value (data) and two pointers (left and right) pointing to the left and right child nodes.
- It includes a helper function createANewNode, which creates a new node and initializes its data and pointers.
- After this, the main function insertNode will insert a new node into the left-skewed binary tree.
- If the tree is empty, a new node is created using createNode, and if not, then, the node is recursively inserted as the left child of the current root.
- Finally, the insertNode function returns the pointer to the root node, ensuring any changes made during the insertion process are reflected in the binary tree structure.

## The basic operation that can be performed on this Tree:

**Search Operation:**For searching a particular element in this tree, we have to traverse the elements of the tree in the direction where all the elements are skewed so that it can be in the right direction or towards the left direction. Once we find the direction, we will traverse the temp node till the end until we can’t find the targeted node.**Insertion Operation:**To insert an element in this tree is very easy; all we have to do is find the exact position of the new node and then add that node to its right position.**Deletion Operation:**Deleting an element from this tree involves two steps: firstly, we have to find the desired element, and secondly, we have to remove that particular node from the tree. In the delete operation, we must ensure that all the other nodes are in their exact position.

However, it is important to note that the worst time complexity of the search, delete, and insert operations in skewed binary trees is O(n), while the best time complexity is O(1).

## Advantages of Skewed Binary Trees :

- This tree is simple to implement and requires less memory than other binary trees.
- Skewed binary trees can naturally sort data, and this property is helpful in such a scenario where maintaining the order of insertion is very important.
- Additionally, skewed binary trees are particularly useful when dealing with skewed or patterned data distributions.

## Disadvantages of Skewed Binary Trees :

- Skewed binary trees are unsuitable for all types of data distributions or search pattern scenarios.
- In searching, comparison can reach up to N number of searches, which can result in higher time complexity. However, to mitigate this issue, we can opt for an AVL-balanced tree.
- Skewed binary trees can perform poorly in specific scenarios because the tree is skewed to one side and act like a linked list data structure. And because of this nature, it performs inefficient search and retrieval operations.

## Applications of Skewed Binary Trees :

- File systems
- Expression evaluation
- Huffman coding
- Compiler Optimization
- Resource Allocation:

And many more.

## FAQs :

**It is possible to balance a skewed binary tree?**

No, skewed binary trees can never be balanced because it has the property of skewed its node in one direction only. It is possible to balance a skewed binary tree.

2. **Are skewed binary trees suitable for storing sorted data? **

No, skewed binary trees are not suitable data structures for sorted data because:

- They can degrade to a linked list.
- Because of the one-direction property, this tree can result in ineffective search operations.

3. **How skewed binary trees differ from balanced binary trees? **

Skewed binary trees have a node towards one side only. Whereas, balanced binary trees have an equal height of nodes on both sides.

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