Aditya Chatterjee's Blog, page 174

Threaded Binary Tree

What is threaded binary tree?

Threaded binary tree is a simple binary tree but they have a speciality that null pointers of leaf node of the binary tree is set to inorder predecessor or inorder successor.

The main idea behind setting such a structure is to make the inorder and preorder traversal of the tree faster without using any additional data structure(e.g auxilary stack) or memory to do the traversal.

Types of Threaded Binary Tree

There are two types of threaded binary tree:

Single T...

Boolean Parenthesization Problem

We will solve Boolean Parenthesization Problem using Dynamic Programming and understand the algorithm with a step by step explanation. The time complexity to solve this problem is O(N^3) with a space complexity of O(N^2).

Given a boolean expression with following symbols.:

'T' ---> true'F' ---> false

And following operators filled between symbols

& ---> boolean AND| ---> boolean OR^ ---> boolean XOR

Count the number of ways we can parenthesize the expression so that the value of exp...

Delete Middle Node from Linked List

In this problem, we will delete the Middle Node from a given Linked List. We have covered the algorithm (along with implementation) to delete the middle node from a Singly Linked List and Doubly Linked List.

We will go through some of the basics of Linked List and the delete operation to remove a given node in a Linked List and then, move to our main topic. The challenge is to identify the node to delete that is the middle node in the given Linked List.

About Linked List

Linked List is a one of ...

Checking if a Binary Tree is foldable

A binary tree is foldable if the left subtree and right subtree are mirror images of each other. An empty tree is also foldable. Below binary trees are foldable since both have a left subtree that is the mirror image of right subtree.

However, below binary tree is not foldable.

We can check if a binary tree is foldable or not in two ways:

By changing the left subtree to its mirror equivalent. Then checking if the mirror is equivalent to te right subtree.Compare and check if right and left s...

Serialization and Deserialization of Binary Tree

We have presented the process of Serialization and Deserialization of Binary Tree where we convert a Binary Tree into a compress form which can be saved in a file and retrieved back.

Serialization is the process of converting the object into bits. This makes it possible to store it in a memory buffer or a file. After serialisation, the bits can be transmitted via signals over computers and networks. On the other hand, Deserialization is the reverse of Serialisation. It converts those bits back t...

Convert a Binary Tree to a Skewed Binary Tree

A simple binary tree can be easily converted into a skewed binary tree. Since we know, the skewed binary tree can be of two types:

Left Skewed Binary TreeRight Skewed Binary Tree

Hence, we can easily convert any binary tree into skewed binary tree.

We can convert binary tree into two types of skewed binary trees:

Increasing Skewed Binary TreesDecreasing Skewed Binary Trees

Consider a binary tree:

Case 1 : Increasing OrderWe will do inorder traversal, as inorder traversal of a Binary Sea...

Check if a Binary Tree is skewed or not

There are two types of skewed binary trees: Left and Right skewed binary trees. From their characteristics we can conclude that they either have one child node or no node at all.

Hence, below given binary tree is skewed.

and below binary tree is not skewed since one of its nodes have two child nodes.

Hence, in its implementation we will recursively check if the nodes of the binary tree have one child nodes or no node. If so, then we will keep traversing else return false on encountering two ch...

Introduction to Skewed Binary Tree

A binary tree can be called a skewed binary tree if all nodes have one child or no child at all. They can be of two types:

Left Skewed Binary TreeRight Skewed Binary TreeLeft Skewed Binary Tree

If all nodes are having a left child or no child at all then it can be called a left skewed binary tree. In this tree all children at right side remain null.

Right Skewed Binary Tree

If all nodes are having a right child or no child at all then it can be called a right skewed binary tree. In this tre...

Basics of Unordered multiset in C++

An unordered multiset is an unordered set (a set in which a key can be stored in any random order) that allows different elements to have equivalent values (allows duplicate items).

How are elements of an Unordered multiset stored internally?
1. The elements of the Unordered multiset are organized into buckets.
2. It uses hashing to insert these elements into buckets.
3. This reduces the access time of an individual element because with the help of hash values we can directly access the buck...

Basic commands for using VIM editor like a Pro

In this guide, we have presented all basic commands that you will need to use VIM editor for doing all tasks efficiently. You will learn how to search for a word, how to replace the word, select, copy, paste, using various special features of VIM and much more. Vim is an editor to create or edit a text file. There are two modes in vim:

Command modeInsert modeIn the command mode, user can move around the file, delete text, etc.In the insert mode, user can insert text.

To create a new file ...