Aditya Chatterjee's Blog, page 173

Reverse a Stack

The objective of this article at OPENGENUS is to explore various approaches that can be used to reverse the given stack (stack is a linear data structure where insertion and deletion are made at the same end).

Various approaches to reverse a stack:

Approach 1: Naive approachApproach 2: Reverse a Stack recursively
Both approaches take O(N) time and O(N) space complexity.Approach 1

1)Naive Approach: The naive approach is to keep on removing the top element from the given stack and pushing it t...

Stacking in Machine Learning

"When there is Unity, there is always victory"

Ensemble modeling is a powerful way to improve the performance of your model. It is a machine learning paradigm where multiple models are trained to solve the same problem and combined to get better results. It is also an art of combining a diverse set of learners together to improvise on the stability and predictive power of the model.

Most common types of Ensemble Methods:

BaggingBoostingStacking

In this article, we will focus on Stacking. B...

Control Flow statements in Ruby

Control flow statements are used for the controlled logical and conditional execution of a statement. All control flow statements are associated with boolean value - it can be either true or false, and depending on that, operates in a given pattern.

Note:
Because of the flexibility of the Ruby language, most of these statements can be used as statement modifiers - which was borrowed from Perl.
There may be different ways to write these statements. It would not be possible to cover all of them, ...

Zig Zag Traversal of Binary Tree

In this article, we present 4 different approaches for Zig Zag Traversal of Binary Tree. The zigzag traversal of the binary tree can be better understood using below example:

For the above tree, the zigzag traversal will be : 1 2 5 6 7 3 4

There are many approaches for this problem like:

We can use two stacks and swap the values of these stacks at each level.We can use deque to solve problem. Depending upon the even or odd level we will push or pop.We can also use recursion. It will print th...

Check if 2 Binary Trees are isomorphic

Two Binary Trees are known as isomorphic if one of them can be obtained from the other one by series of flipping of nodes, swapping the children both left and right of number of nodes. Any number of nodes at all levels can swap their child nodes.

With above definition we can say that two empty trees are isomorphic.
Let us consider an example:

Above trees are isomporhpic.
We can swap node 2 and 3. Then we can swap node NULL and 6. Then finally we can swap node 7 and 8.
We have two main approache...

Convert Binary Tree to Circular Doubly Linked list

To convert binary tree to circular doubly linked list, we will take left node as previous pointer and right node as next pointer. The order of nodes in Doubly Linked List must be same as in inorder of the given binary tree. The very first node of inorder traversal will become the head of the doubly linked list.

In the above binary tree, we will get the doubly linked list as follows:

We need to check following conditions:

If left subtree exists then process left subtree to DLL. We will use rec...

Succinct (0-1) Encoding of Binary Tree

Succinct encoding is an approach to encode a Binary Tree to the lowest possible space and maintain the structural information. The number of structurally different binary trees on n nodes is nth Catalan's Number. Catalan numbers are a sequence of natural numbers that occur in various problems like counting the possible Binary Search trees with n values, counting the number of binary trees with n+1 leaves etc. Some Catalan numbers for n = 0, 1, 2, 3 ... are 1, 1, 2, 5 ...
They can be found using ...

LCA in Binary Tree using Euler tour and Range Minimum Query

In this problem, we will find the Lowest Common Ancestor of a Binary Tree using Euler tour and Range Minimum Query. We can solve the LCA problem by reducing it to a RMQ problem. There are many approaches to find the LCA of nodes but have different space and time complexities. This is the most efficient approach.

Range Minimum Query is used on arrays to find the position of an element with minimum value between two specified indices. There are many approaches to implement Range Minimum Query meth...

Lowest Common Ancestor in a Binary Tree

In binary trees, for given two nodes a and b, the lowest common ancestor is the node of which both a and b are descendants. Here a node can be descendant of itself.

In the above image, if we consider two nodes 2 and 3 then their lowest common ancestor will be node 1.
Similarly, the lowest common ancestor of 4 and 5 will be 2 and that of 3 and 4 would be 1.
The lowest common ancestor is the common and shared descendant of both given nodes.
LCA is used in many other binary tree problems like in d...

Operations in Threaded Binary Tree

There are three main operations which can be done on a threaded binary tree:

InsertSearchDelete

In these operations I'm using a doubly threaded binary tree let's look at them one by one:

Insert in Threaded Binary Tree

If we want to insert new node in threaded binary tree then we can use insert operation.

To insert any node in threaded binary tree three cases might arise

1.When new node is inserted in a empty tree.
2.When new node is inserted as left child of some node in the tree.
3.When new...