← prev next →

DS Tutorial
Advertisement

DS Tutorial Mygraduaid

DS Introduction Get Help from Skilled Experts

DS Algorithm Get expert tutor support anytime

Asymptotic Analysis

DS Pointer Red-black tree in Data Structure

DS Structure The red-Black tree is a binary search tree. The prerequisite of the
red-black tree is that we should know about the binary search tree.
In a binary search tree, the values of the nodes in the left subtree
should be less than the value of the root node, and the values of
DS Array
the nodes in the right subtree should be greater than the value of
the root node.
DS Array
Each node in the Red-black tree contains an extra bit that
2D Array
represents a color to ensure that the tree is balanced during any
operations performed on the tree like insertion, deletion, etc. In a
binary search tree, the searching, insertion and deletion take
DS Linked List O(log2n) time in the average case, O(1) in the best case and O(n) in
the worst case.
Linked List
Let's understand the different scenarios of a binary search tree.
Types of Linked List

Singly Linked List

Doubly Linked List

Circular Linked List

Circular Doubly List

Skip list in DS

DS Stack

DS Stack

Array Implementation
In the above tree, if we want to search the 80. We will first compare
Linked List Implementation 80 with the root node. 80 is greater than the root node, i.e., 10, so
searching will be performed on the right subtree. Again, 80 is
compared with 15; 80 is greater than 15, so we move to the right of

DS Queue the 15, i.e., 20. Now, we reach the leaf node 20, and 20 is not equal
to 80. Therefore, it will show that the element is not found in the
tree. After each operation, the search is divided into half. The above
:
 BST will take O(logn) time to search the element.
DS Queue

Types of Queues

Array Representation

Linked List Representation

Circular Queue

Deque

Priority Queue

DS Tree

DS Tree

Binary Tree

Binary Search Tree

AVL Tree

B Tree

B+ Tree

Red-black tree

DS Graph
The above tree shows the right-skewed BST. If we want to search
the 80 in the tree, we will compare 80 with all the nodes until we
DS Graph
find the element or reach the leaf node. So, the above right-
Graph Implementation skewed BST will take O(N) time to search the element.

BFS Algorithm
In the above BST, the first one is the balanced BST, whereas the
DFS Algorithm second one is the unbalanced BST. We conclude from the above

Spanning Tree two binary search trees that a balanced tree takes less time than
an unbalanced tree for performing any operation on the tree.
a)Prim's Algorithm

b)Kruskal's Algorithm Therefore, we need a balanced tree, and the Red-Black tree is a
self-balanced binary search tree. Now, the question arises that why
do we require a Red-Black tree if AVL is also a height-balanced
tree. The Red-Black tree is used because the AVL tree requires
DS Searching
many rotations when the tree is large, whereas the Red-Black tree
requires a maximum of two rotations to balance the tree. The main
Linear Search difference between the AVL tree and the Red-Black tree is that the
Binary Search AVL tree is strictly balanced, while the Red-Black tree is not
completely height-balanced. So, the AVL tree is more balanced
than the Red-Black tree, but the Red-Black tree guarantees
O(log2n) time for all operations like insertion, deletion, and
DS Sorting
searching.

Bubble Sort Insertion is easier in the AVL tree as the AVL tree is strictly
balanced, whereas deletion and searching are easier in the Red-
Bucket Sort
:
 Comb Sort Black tree as the Red-Black tree requires fewer rotations.

Counting Sort As the name suggests that the node is either colored in Red or
Heap Sort Black color. Sometimes no rotation is required, and only recoloring
is needed to balance the tree.
Insertion Sort

Merge Sort Properties of Red-Black tree

Quick Sort It is a self-balancing Binary Search tree. Here, self-

Radix Sort balancing means that it balances the tree itself by either
doing the rotations or recoloring the nodes.
Selection Sort

Shell Sort
This tree data structure is named as a Red-Black tree as
each node is either Red or Black in color. Every node
Bitonic Sort
stores one extra information known as a bit that
Cocktail Sort represents the color of the node. For example, 0 bit

Cycle Sort denotes the black color while 1 bit denotes the red color
of the node. Other information stored by the node is
Tim Sort
similar to the binary tree, i.e., data part, left pointer and
right pointer.

In the Red-Black tree, the root node is always black in

Differences
color.

Linear vs non-linear In a binary tree, we consider those nodes as the leaf

which have no child. In contrast, in the Red-Black tree,
Array vs linked list
the nodes that have no child are considered the internal
Stack vs queue
nodes and these nodes are connected to the NIL nodes
Linear vs Circular Queue that are always black in color. The NIL nodes are the leaf

Linear Search vs Binary Search nodes in the Red-Black tree.

Singly Linked List vs Doubly If the node is Red, then its children should be in Black
Linked List color. In other words, we can say that there should be no
Binary vs Binary Search Tree red-red parent-child relationship.

Tree vs Graph Every path from a node to any of its descendant's NIL
Binary Search tree vs AVL tree node should have same number of black nodes.

Red Black Tree vs AVL tree

Is every AVL tree can be a Red-Black tree?
B tree vs B+ tree
Yes, every AVL tree can be a Red-Black tree if we color each node
Quick Sort vs Merge Sort either by Red or Black color. But every Red-Black tree is not an AVL
because the AVL tree is strictly height-balanced while the Red-
BFS vs DFS
Black tree is not completely height-balanced.
Stack vs Heap

Bubble sort vs. Selection sort

Stack vs Array

Full Binary Tree vs Complete

Binary Tree

Binary Tree vs B Tree

Primitive vs non-primitive data

structure

Data types vs data structure

:
 Insertion in Red Black tree
Misc The following are some rules used to create the Red-Black tree:

1. If the tree is empty, then we create a new node as a root node with
Trie Data Structure
the color black.
Heap Data Structure 2. If the tree is not empty, then we create a new node as a leaf node

Splay Tree with a color red.

3. If the parent of a new node is black, then exit.
Fundamental of the DS
4. If the parent of a new node is Red, then we have to check the color
Hash Table
of the parent's sibling of a new node.
Preorder Traversal
4a) If the color is Black, then we perform rotations and recoloring.
Tree Traversal
4b) If the color is Red then we recolor the node. We will also check
Implementation of Queue using
Stacks whether the parents' parent of a new node is the root node or not;
if it is not a root node, we will recolor and recheck the node.
Implementation of Stack using
Queue
Let's understand the insertion in the Red-Black tree.
Binomial Heap
10, 18, 7, 15, 16, 30, 25, 40, 60
Postorder Traversal
Step 1: Initially, the tree is empty, so we create a new node having
Sparse Matrix
value 10. This is the first node of the tree, so it would be the root
Detect loop in a Linked list
node of the tree. As we already discussed, that root node must be
Inorder Traversal black in color, which is shown below:

Convert Infix to Postfix notation

Convert infix to prefix notation

Conversion of Prefix to Postfix

expression

Conversion of Postfix to Prefix

expression Step 2: The next node is 18. As 18 is greater than 10 so it will come
at the right of 10 as shown below.
Remove the loop in a Linked List

Implement two stacks in an array

Reverse a stack using recursion

Detect cycle in a directed graph

Optimal Binary Search Tree

Priority Queue using Linked list

Balanced Binary Search Tree

Boundary Traversal of Binary tree

Diagonal Traversal of Binary Tree

Vertical Traversal of a Binary tree

Graph Algorithms

Time Complexity of Sorting

Algorithms

Applications of Stack in Data

Structure

Dictionary Data Structure

:
 Structured Data and
Unstructured Data

List Data Structure

Types of Tree in Data Structure

Abstract data type in data

structure

Disjoint set data structure

Dynamic Data Structure

Hash Function in Data Structure We know the second rule of the Red Black tree that if the tree is
Complete Binary Tree not empty then the newly created node will have the Red color.
Therefore, node 18 has a Red color, as shown in the below figure:
Threaded Binary Tree

Diameter of Binary Tree Now we verify the third rule of the Red-Black tree, i.e., the parent of
the new node is black or not. In the above figure, the parent of the
Height of Binary Tree
node is black in color; therefore, it is a Red-Black tree.
Inorder Tree Traversal without
Stack Step 3: Now, we create the new node having value 7 with Red

Enumeration of Binary Trees

color. As 7 is less than 10, so it will come at the left of 10 as shown
below.
Maximum Width of a Binary Tree

Types of Graph in Data Structure

Primitive Data Type

Semi-Structured Data

Advance Data Structures

Sort an Array of 0's, 1's, and 2's

Stock Span Problem

Implementation of Deque by
Circular Array

Rotate Operation in Linked List

Subarray with given sum

Self-organizing List

Unrolled Linked List

Types of Sparse Matrices

Application of Linked List

Topological Sorting

Ternary Search Tree

Stock Span Problem

Treap Data Structure

Quicksort on Doubly Linked List

Inversion count

Expression tree in DS

Garbage Collection in DS
:
 Merge Sort on Doubly Linked
List

Sort Stack using Recursion Now we verify the third rule of the Red-Black tree, i.e., the parent of
the new node is black or not. As we can observe, the parent of the
LIFO Approach in data structure
node 7 is black in color, and it obeys the Red-Black tree's
Big O Notation in DS properties.
Binary Tree Traversal in DS
Step 4: The next element is 15, and 15 is greater than 10, but less
Queue Operations in DS than 18, so the new node will be created at the left of node 18. The
What is a Non-Linear Data node 15 would be Red in color as the tree is not empty.
Structure

FIFO Approach in data structure

What are connected graphs in

data structure

Which Python data structure is

immutable

Which data structure is used by

map

What is iteration in data

structure

What are linear search and

binary search in data structure
The above tree violates the property of the Red-Black tree as it has
Hash Table vs STL Map
Red-red parent-child relationship. Now we have to apply some rule
Recaman's Sequence to make a Red-Black tree. The rule 4 says that if the new node's

Maximum area rectangle parent is Red, then we have to check the color of the parent's
created by selecting four sides sibling of a new node. The new node is node 15; the parent of the
from an array new node is node 18 and the sibling of the parent node is node 7.
Maximum number of distinct As the color of the parent's sibling is Red in color, so we apply the
nodes in a root-to-leaf path rule 4a. The rule 4a says that we have to recolor both the parent

Hashing - Open Addressing for and parent's sibling node. So, both the nodes, i.e., 7 and 18, would
Collision Handling be recolored as shown in the below figure.

Introduction to Hashing

Separate chaining for Collision

Handling

Check if a given array contains

duplicate elements within k
distance from each other

Given an array A[] and a number

x, check for pair in A[] with sum
as x (aka Two Sum)

Find number of Employees

Under every Manager

Union and Intersection of two

Linked Lists

Kth Largest element in an array

Sort an almost-sorted, k-sorted

or nearly-sorted array We also have to check whether the parent's parent of the new

Fibonacci Heap node is the root node or not. As we can observe in the above
:
 Find whether an array is subset figure, the parent's parent of a new node is the root node, so we do
of another array not need to recolor it.

Print a Binary Tree in Vertical

Step 5: The next element is 16. As 16 is greater than 10 but less than
Order
18 and greater than 15, so node 16 will come at the right of node 15.
Tournament Tree (Winner Tree) The tree is not empty; node 16 would be Red in color, as shown in
Lazy Propagation in Segment the below figure:
Tree

Segment Tree - Range Minimum

Query

Segment Tree - Sum of given

Range

2-3 Trees (Search, Insertion, and

Deletion)

Print kth least significant bit of a

number

Add two numbers represented

by linked lists

Adding one to the number

represented as array of digits

Find precedence characters form

a given sorted dictionary

Check if any anagram of a string In the above figure, we can observe that it violates the property of
is palindrome or not the parent-child relationship as it has a red-red parent-child
Minimum Insertions to form a relationship. We have to apply some rules to make a Red-Black
Palindrome tree. Since the new node's parent is Red color, and the parent of

Allocate Minimum Number of the new node has no sibling, so rule 4a will be applied. The rule 4a
Pages says that some rotations and recoloring would be performed on
the tree.
Assembly Line Scheduling

Breadth First Search or BFS for a Since node 16 is right of node 15 and the parent of node 15 is node
Graph 18. Node 15 is the left of node 18. Here we have an LR relationship,
Find an element in array such so we require to perform two rotations. First, we will perform left,
that sum of the left array is equal and then we will perform the right rotation. The left rotation would
to the sum of the right array be performed on nodes 15 and 16, where node 16 will move
Bridges in a Graph upward, and node 15 will move downward. Once the left rotation is
performed, the tree looks like as shown in the below figure:
Bubble Sort in JavaScript

Burn the Binary tree from the

Target node

Lowest Common Ancestor in a

Binary Search Tree

Types of Hash Functions in C

Implement Dynamic Deque

using Templates Class and a
Circular Array

Iterative Depth First Traversal of

Graph

Linked List Data Structure in C++

With Illustration
:
 Reverse a Linked List in Groups
of Given Size

Reverse Alternate K nodes in a

Singly Linked List

When should I use a List vs a

LinkedList

Why is deleting in a Singly

Linked List O(1)

Construct Full Binary Tree using

its Preorder Traversal and
Preorder Traversal of its Mirror
Tree

Find Relative Complement of

two Sorted Arrays

Handshaking Lemma and

Interesting Tree Properties -DSA

How to Efficiently Implement

kStacks in a Single Array In the above figure, we can observe that there is an LL relationship.
The above tree has a Red-red conflict, so we perform the right
Write C Functions that Modify
Head Pointer of a Linked List rotation. When we perform the right rotation, the median element
would be the root node. Once the right rotation is performed,
Introduction to Ant Colony
Optimization
node 16 would become the root node, and nodes 15 and 18 would
be the left child and right child, respectively, as shown in the below
What is Array
figure.
The practical Byzantine Fault
Tolerance (pBFT)

Applications of Queue Data

Structure

Line Graph

Symmetric Binary Tree

AVL Tree Advantages

AVL Tree Time Complexity

Merge Two Binary Trees

Stack Operations in Data

Structure

Self-Balancing Binary Search

Trees

Sliding Window Maximum

(Maximum of all Subarrays of size
K)

AVL Trees Operations

Limitations of Stack in Data

Structures

Representation of stack in data

structure

Advantages of Threaded Binary

Tree
:
 Serialize and Deserialize a Binary After rotation, node 16 and node 18 would be recolored; the color of
Tree node 16 is red, so it will change to black, and the color of node 18 is

Application of Binary Tree black, so it will change to a red color as shown in the below figure:

AVL Tree Applications

B Tree Visualization

Properties of AVL Trees

Push and Pop Operation in Stack

in Data Structure

Binary Search Tree

Implementation

Find Maximum Sum by

Replacing the Subarray in Given
Range

Find The Number N, Where

(N+X) Divisible By Y And (N-Y)
Divisible By X

Find Values of P and Q Satisfying

the Equation N = P^2.Q

What is the Balance Factor of Step 6: The next element is 30. Node 30 is inserted at the right of
AVL Tree node 18. As the tree is not empty, so the color of node 30 would be
AVL Tree Implementation in red.
Golang

Concatenation of two Linked

Lists in O(1) time

Find Minimum Area of

Rectangle Formed from Given
Shuffled Coordinates

Find the Length of Maximum

Path in Given Matrix for Each
Index

How to Parse an Array of Objects

in C++ Using RapidJson

Largest BST in Binary Tree

How to Print String Literal and

Qstring With Qdebug in C++

Properties of Binary Tree

Right View of Binary Tree

Strict Binary Tree

The color of the parent and parent's sibling of a new node is Red,
Difference between Comb Sort
so rule 4b is applied. In rule 4b, we have to do only recoloring, i.e.,
and Shell Sort
no rotations are required. The color of both the parent (node 18)
Full Binary Tree and parent's sibling (node 15) would become black, as shown in
Left View of a Binary Tree the below image.

Level order Traversal in a Binary

Tree

Lowest Common Ancestor of a

Binary Tree
:
 Top View of a Binary Tree

Types of Binary Trees

B Tree Insertion

Evaluation of a Postfix notation

B+ Tree Insertion

Bottom View of a Binary Tree

AVL Tree Program in C

B Tree Applications

B Tree Properties

How to Search, Insert, and Delete

in an Unsorted Array

Count Non-Leaf Nodes in a

Binary Tree

Get the Level of a Given Key in a

Binary Tree
We also have to check the parent's parent of the new node,
Double Ended Priority Queue whether it is a root node or not. The parent's parent of the new

B+ Tree Deletion node, i.e., node 30 is node 16 and node 16 is not a root node, so we
will recolor the node 16 and changes to the Red color. The parent
B+ Tree Insertion
of node 16 is node 10, and it is not in Red color, so there is no Red-
Checking for the Mirror Images red conflict.
in the Binary Trees

Count Non-Leaf Nodes in a

Binary Tree

Get a Parent Binary Tree

Get All Descendants of the

Binary Tree Element

Get the Level of a Given Key in a

Binary Tree

Flatten Binary Tree to Linked List

Formula to Find a Level of the

Node in a Binary Tree

Substring with Maximum

Number of Vowels of Given
Length (k)

Flatten Binary Tree to Sorted

Linked List

Floor and Ceiling in Binary

Search Tree Step 7: The next element is 25, which we have to insert in a tree.

Find Level in a Binary Tree with Since 25 is greater than 10, 16, 18 but less than 30; so, it will come at
Max Sum the left of node 30. As the tree is not empty, node 25 would be in
Red color. Here Red-red conflict occurs as the parent of the newly
Find kth Smallest Element in a
Binary Search Tree created is Red color.

Find Next Greater Element in Since there is no parent's sibling, so rule 4a is applied in which
Binary Tree
rotation, as well as recoloring, are performed. First, we will perform
Hashing in Data Structure rotations. As the newly created node is at the left of its parent and
the parent node is at the right of its parent, so the RL relationship
:
 Primitive Data Structure is formed. Firstly, the right rotation is performed in which node 25
goes upwards, whereas node 30 goes downwards, as shown in the
Find if Binary Tree Satisfies
Balanced Height Property below figure.

Find the Largest Perfect Binary

Tree in a Given Tree

Find Immediate Parents of Two

Nodes in a Binary Tree

Applications, Advantages and

Disadvantages of Circular
Doubly linked List

Sorting Techniques in Data

Structures

Find Clockwise Array in Binary

Search Tree

Find Duplicate Subtrees in

Binary Tree

Find the Index of the Number

Using a Binary Tree

Find the In-Order Successor of a

Node in a Binary Tree
After the first rotation, there is an RR relationship, so left rotation is
Reversing a Queue
performed. After right rotation, the median element, i.e., 25 would
Different Types of Stack
be the root node; node 30 would be at the right of 25 and node 18
Operations
would be at the left of node 25.
Time Complexity in Data
Structure

Arrays are best Data Structure

Dynamic memory allocation in

Data Structure

Application of Data Structure

Applications of Tree in Data

Structure

How to Check if a Binary

Number is Divisible by 3

Stock Buy and Sell Problem

Find Minimum in Rotated Sorted

Array

Interpolation Search vs. Binary

Search

Boggle (find all possible words in

a board of characters)

Difference Between Prim's and

Kruskal's algorithm

Interpolation Search

Quick Sort Using Hoare's

Partition

Longest common substring

:
 Longest Repeated Substring

Substring Check

Clone a Binary Tree with

Random Pointers

How to efficiently implement k

stacks in a single array

Kasai's algorithm for

construction of LCP array from
Suffix array

Strassen's Matrix Multiplication

suffix array introduction

Suffix Array nLogn Algorithm

Suffix tree introduction

Binary indexed tree

Given a n x n square matrix, find

the sum of all sub-squares of size Now recoloring would be performed on nodes 25 and 18; node 25
kxk
becomes black in color, and node 18 becomes red in color.
Inplace MxN size matrix
transpose

longest palindrome substring

Maximum Size Square Sub-

matrix with all 1s

Maximum Sum Rectangle in a

2D Matrix

Printing All Elements in Sorted

Order from Row and Column
Wise Sorted Matrix

Arraylist vs linked list

Diameter of an N-ary Tree

Generic Trees (N-ary Trees)

Level Order Traversal of N-ary

Tree

Mirror of n-ary Tree

Serialize and Deserialize an N-ary Step 8: The next element is 40. Since 40 is greater than 10, 16, 18,
Tree 25, and 30, so node 40 will come at the right of node 30. As the tree
Sum of all elements of N-ary Tree is not empty, node 40 would be Red in color. There is a Red-red
conflict between nodes 40 and 30, so rule 4b will be applied.
The Great Tree-List Recursion
Problem

Two dimensional Binary Indexed

Tree or Fenwick Tree

Binary Indexed Tree Range

Updates and Point Queries

Binary Indexed Tree Range

Updates and Range Queries
:
 Closest greater or same value on
left side for every element in
array

Construct an array from its pair-

sum array

Equilibrium index of an array

Fermat's Factorization Method in

Java

Find a triplet that sum to a given

value in an array

Find k numbers with most

occurrences in the given array

Find maximum value of

Sum(i*arr[i]) with only rotations
on given array allowed

Handshaking Lemma and

Interesting Tree Properties
As the color of parent and parent's sibling node of a new node is
Implementation of Dynamic
Red so recoloring would be performed. The color of both the
Segment Trees with Poly Hash
Tables nodes would become black, as shown in the below image.

Majority Element After recoloring, we also have to check the parent's parent of a new

Maximum equilibrium sum in an node, i.e., 25, which is not a root node, so recoloring would be
array performed, and the color of node 25 changes to Red.

Maximum profit by buying and

After recoloring, red-red conflict occurs between nodes 25 and 16.
selling a share at most twice
Now node 25 would be considered as the new node. Since the
Median in a stream of integers parent of node 25 is red in color, and the parent's sibling is black in
(running integers)
color, rule 4a would be applied. Since 25 is at the right of the node
Merge Sort Tree for Range Order 16 and 16 is at the right of its parent, so there is an RR relationship.
Statistics
In the RR relationship, left rotation is performed. After left rotation,
Merge two sorted arrays with the median element 16 would be the root node, as shown in the
O(1) extra space below figure.
Minimum increment by k
operations to make all elements
equal

Minimum number of jumps to

reach end

MO's Algorithm

Search in a row-wise and

column-wise sorted matrix

Smallest subarray with sum

greater than a given value

Sparse Table

Square Root (Sqrt)

Decomposition Algorithm

Two Pointers Technique

Compressed segment trees and

merging sets in O(N*logN)
:
 Intersection of Linked List After rotation, recoloring is performed on nodes 16 and 10. The
color of node 10 and node 16 changes to Red and Black,
Intersection Point in Y shaped
linked list respectively as shown in the below figure.

Make Array Zero By Subtracting

Equal Amounts In Java

Maximum Sum Pair with Equal

Highest Digits

Minimum Possible value of |ai +

aj - k| for given array and k

Tango Tree Data Structure

Check if two arrays are equal or

not

Construct BST from its given

level order traversal

Elements to be added so that all

elements of a range are present
in the array

Find Missing Elements in Range

K-th Largest Sum Contiguous

Subarray

Minimum number of subsets

with distinct elements

Minimum product of k integers

in an array of positive integers

The non-overlapping sum of two

sets

Palindrome substring queries

Recaman's Sequence

The sum of Elements Between

k1th and k2th smallest elements

Print Matrix in a Snake Pattern

An Interesting Method to
Generate Binary Numbers from 1
to n

Bottom View of a Binary Tree

Circular List Application

Deleting a Node in a Linked List

Diameter of a Binary Tree

Step 9: The next element is 60. Since 60 is greater than 16, 25, 30,
Find distance between two
and 40, so node 60 will come at the right of node 40. As the tree is
nodes of a Binary Search Tree
not empty, the color of node 60 would be Red.
Inorder Tree Traversal without
Recursion As we can observe in the above tree that there is a Red-red conflict
occurs. The parent node is Red in color, and there is no parent's
Inorder Tree Traversal without
recursion and stack! sibling exists in the tree, so rule 4a would be applied. The first
rotation would be performed. The RR relationship exists between
Maximum product of indexes of
next greater on left and right the nodes, so left rotation would be performed.
:
 Print Left View of a Binary Tree

Remove all leaf nodes from the

binary search tree

Sort a stack using a temporary

stack

Split a Circular List into 2 Halves

Check given array of size n can

represent BST of n levels or not

Construct a linked list from 2D

matrix

In place, convert BST into a Min-

Heap

Polish and Reverse Polish When left rotation is performed, node 40 will come upwards, and
Notation
node 30 will come downwards, as shown in the below figure:
Suffix Trees in data structure

Weight Balanced Binary Tree

Transform a BST to greater sum

tree

Vertical order traversal of Binary

Tree using Map

Application of heap tree

Construct a linked list from 2D

matrix

Define Abstract Data Type in

Data Structure

Detect and Remove Loop in a After rotation, the recoloring is performed on nodes 30 and 40. The
Linked List
color of node 30 would become Red, while the color of node 40
Difference Between a Tree and a would become black.
Forest in Data Structures

Difference between bubble sort

and merge sort

Difference between merge sort

and quick sort

Explain double ended queue in

detail

Find the median from running

data stream

Flattening a Linked List

Generate All Subarrays

Heap memory vs. stack memory

The above tree is a Red-Black tree as it follows all the Red-Black
Huffman encoding tree properties.

Huffman Tree in Data Structure

Deletion in Red Back tree
Implementation of Graph in
Let's understand how we can delete the particular node from the
JavaScript
Red-Black tree. The following are the rules used to delete the
K-D Tree in Data Structures particular node from the tree:
:
 Knapsack Problem in Data Step 1: First, we perform BST rules for the deletion.
Structure
Step 2:
Largest Sum Contiguous
Subarray (Kadane's Algorithm) Case 1: if the node is Red, which is to be deleted, we simply delete
Multiway Trees in Data it.
Structures
Let's understand case 1 through an example.
Optimal binary search tree in
data structure Suppose we want to delete node 30 from the tree, which is given
polynomial addition in data below.
structure

Postfix deferred queue

Properties of tree in data

structure

Recurrence Relation of Merge

Sort

Recursive Bubble Sort

RSS linked list

Search in a Rotated Sorted Array

Sort an array of 0s, 1s and 2s |

Dutch National Flag problem

Assign directions to edges so

that the directed graph remains
acyclic

Dependency Graph Initially, we are having the address of the root node. First, we will
apply BST to search the node. Since 30 is greater than 10 and 20,
Diameter of an N-ary tree
which means that 30 is the right child of node 20. Node 30 is a leaf
Height of n-ary tree if parent
node and Red in color, so it is simply deleted from the tree.
array is given

Introduction to Heavy Light If we want to delete the internal node that has one child. First,
Decomposition replace the value of the internal node with the value of the child
node and then simply delete the child node.
LCA in a binary tree using RMQ

Number of Siblings of a given Let's take another example in which we want to delete the
node in n-arr tree internal node, i.e., node 20.
Number of ways to traverse an
N-arr

XOR Linked List - A Memory

Efficient Doubly Linked List

Callback Queue

Inorder Predecessor and

Successor in a Binary Search
Tree

What is Internal Sorting

Block Swap Algorithm for Array

Rotation in Python

CHECK FOR BALANCED

BRACKETS IN AN EXPRESSION
(WELL FORMEDNESS)
:
 Count pairs from two BSTs
whose sum is equal to given
value x

Counting Inversions Problem in

Data Structure

Differences between Insertion

Sort and Selection Sort

LEFTIST TREE / LEFTIST HEAP

Find if there is a triplet in a

balanced bst that adds to zero

Find the Maximum English

Letter Present in Both Lowercase
and Uppercase

K-way Merge Sort

Perfect Binary Trees We cannot delete the internal node; we can only replace the value

Reverse Sort of that node with another value. Node 20 is at the right of the root
node, and it is having only one child, node 30. So, node 20 is
Scapegoat Trees
replaced with a value 30, but the color of the node would remain
Stack Organisation the same, i.e., Black. In the end, node 20 (leaf node) is deleted from
Time Complexity of using heap the tree.

Two-way merge sort

Validity of a given Tic-Tac-Toe

board configuration

Weighted Prefix Search

Binary Tree to CDLL

Check if a Binary Tree is a

Subtree of Another Binary Tree

Check if the Given String of

Words can be Formed from
Words Present in the Dictionary

Count sort vs bucket sort

FIFO vs LIFO approach in

Programming

If you are given two traversal

sequences, can you construct
the binary tree

Linked List Deletion (Deleting a

key at a given position)

Mastering Bracket Problems for

Competitive Programming

Merge Overlapping Intervals

MIRROR OF MATRIX ACROSS

DIAGONAL

Pair of strings having longest If we want to delete the internal node that has two child nodes. In
common prefix of maximum this case, we have to decide from which we have to replace the
length in given array
value of the internal node (either left subtree or right subtree). We
have two ways:
:
 Print all Possible Combinations Inorder predecessor: We will replace with the largest
of Words from the Dictionary
value that exists in the left subtree.
using Trie

Segment Tree (Range Maximum Inorder successor: We will replace with the smallest
Query with Node Update) value that exists in the right subtree.

Tree Vertex Splitting in data

structure Suppose we want to delete node 30 from the tree, which is shown
below:
Why is Binary Heap Preferred
over BST for Priority Queue

Arrange Consonants and Vowels

in a linked list

Copy a linked list with next and

arbit pointer

Kahn's Algorithm vs DFS

Approach: A Comparative
Analysis

Minimum flip required to make

Binary Matrix symmetric

Sorted insert for circular linked

list

C++ Program for Arranging

Single Linked List in Alternate
Odd and Even Nodes Order
Node 30 is at the right of the root node. In this case, we will use the
Reservoir sampling in C++
inorder successor. The value 38 is the smallest value in the right
0/1 Knapsack using Least Cost subtree, so we will replace the value 30 with 38, but the node
Branch and Bound
would remain the same, i.e., Red. After replacement, the leaf node,
Merge K Sorted Linked Lists i.e., 30, would be deleted from the tree. Since node 30 is a leaf node
using Min Heap and Red in color, we need to delete it (we do not have to perform
Number of elements greater any rotations or any recoloring).
than K in the range L to R using
Fenwick Tree (Offline queries)

Detect Cycle in Graph using DSU

Merkle Tree and Hash Chain

Data Structures with a difference

Create a matrix with alternating

rectangles of O and X

Find the first non-repeating

character from a stream of
characters

Find the first circular tour that

visits all petrol pumps Case 2: If the root node is also double black, then simply remove
the double black and make it a single black.
Find the tasks completed by
soldiers based on their ranks

K-th Largest Sum Contiguous

Subarray

Numbsubarrayer of elements
less than or equal to a given
number in a given
:
 Queries to add, remove and
return the difference of
maximum and minimum

Time Complexity of building a

heap Case 3: If the double black's sibling is black and both its children
Build linear type suffix are black.

Count of Valid Splits in a String

Remove the double black node.
Delete all occurrences of a given
key in a linked list Add the color of the node to the parent (P) node.

Design a data structure that

1. If the color of P is red then it becomes black.
supports insert, delete, search
and getRandom in constant 2. If the color of P is black, then it becomes double black.
time
The color of double black's sibling changes to red.
Find the largest subarray with 0
sum
If still double black situation arises, then we will apply
Free Tree in Data Structures other cases.

How to insert Strings into an AVL

Tree Let's understand this case through an example.

Longest Consecutive Suppose we want to delete node 15 in the below tree.

Subsequence

Merge two binary Max Heaps

Secure Message Encoding

Sort an almost sorted array

Tree of Space - Locking and

Unlocking N-Ary Tree

Triply Linked list

COUNT OF ZEROES

Design a Chess Game

Design a data structure that

supports insert, delete, search
and getRandom in constant
We cannot simply delete node 15 from the tree as node 15 is Black
time
in color. Node 15 has two children, which are nil. So, we replace the
Design and Implement Special 15 value with a nil value. As node 15 and nil node are black in color,
Stack Data Structure
the node becomes double black after replacement, as shown in
Enhancing Password Strength the below figure.

Enumeration of Binary Tree

Eulerian and Hamiltonian path

Fair Array Removal Indices

Find the Absolute Difference

between the Right View Sum of
two Binary Trees

Find the number of colored

nodes according to given queries
in a full Binary Tree

Finding Minimum Steps in

Special Binary Tree
:
 Finding the Largest Multiple of In the above tree, we can observe that the double black's
Three sibling is black in color and its children are nil, which are also

Flatten a binary tree into linked black. As the double black's sibling and its children have black so
list it cannot give its black color to neither of these. Now, the double
black's parent node is Red so double black's node add its black
General Tree (Each node can
have arbitrary number of color to its parent node. The color of the node 20 changes to black
children) Level Order Traversal while the color of the nil node changes to a single black as shown

Generating the Maximum in the below figure.

Number from Two Arrays

Hashing and its Applications

Islands in a graph using BFS

Iterative Letter Combinations of

a Phone Number

K-way Merge Sort

Maximize Total Score

PERMUTED ROWS IN A MATRIX

Remove extra edge from a BST

Van Emde Boas Tree

Which Minimum Spanning Tree After adding the color to its parent node, the color of the double
Algorithm is better black's sibling, i.e., node 30 changes to red as shown in the below
Ackermann Function figure.

BINARY TO SYMMETRIX In the above tree, we can observe that there is no longer double
INPLACE MATRIX TRANSPOSE black's problem exists, and it is also a Red-Black tree.

Print all words matching a Case 4: If double black's sibling is Red.

pattern in CamelCase Notation
Dictionary Tutorials Interview Compiler
Swap the color of its parent and its sibling.
Reduce the string by removing K
consecutive identical characters Rotate the parent node in the double black's direction.
Home Python Java JavaScript HTML SQL PHP C# C++ DS
Subtraction in Linked List Reapply cases.
TRANSITIONS OF MATRIX
Let's understand this case through an example.
Blending vs Stacking

Bloom Filters Suppose we want to delete node 15.

Count Array Pairs Divisible by k

Counting Beautiful Numbers in a

Specified Range

Find the Closest Palindrome

Minimizing water collection

distance in javaT village

Minimum Array Length After Pair

Removals

Nth even Fibonacci Sequence

Persistent Data Structure

Queue for Competitive Initially, the 15 is replaced with a nil value. After replacement, the
Programming node becomes double black. Since double black's sibling is Red so
:
 Recursively remove all adjacent color of the node 20 changes to Red and the color of the node 30
duplicates changes to Black.

Remove the letter to equalize

Once the swapping of the color is completed, the rotation towards
the frequency
the double black would be performed. The node 30 will move
Chocolate Distribution Problem upwards and the node 20 will move downwards as shown in the
Find out the person who got the below figure.
ticket last problem in queue

Product Array Puzzle

MCQs on backtracking

Design a data structure that

supports insert, delete, search,
and getRandom in constant
time

Assign directions to edges so

that the directed graph remains
acyclic

Print the frequency of each

character in Alphabetical order

Check if a queue can be sorted

into another queue using a stack

Auto-complete feature using Trie

Connect nodes at same level

Construct Tree from Given

Inorder and Preorder Traversals

Decimal Equivalent of Binary

Linked List

How do you implement Stack

using Priority Queue or Heap
In the above tree, we can observe that double black situation still
Introduction to Monotonic
Stacks exists in the tree. It satisfies the case 3 in which double black's
sibling is black as well as both its children are black. First, we
Minimum Initial Points to Reach
Destination remove the double black from the node and add the black color to
its parent node. At the end, the color of the double black's sibling,
Print Ancestors of a given node
i.e., node 25 changes to Red as shown in the below figure.
in Binary Tree

Priority Queue using Doubly

Linked List

Shortest distance between two

cells in a matrix or grid

Sort an Array in Wave Form

Burn the binary tree starting

from the target node

Check for possible paths in the

2D Matrix

Find Triplets with zero-sum

Print a Given Matrix in Spiral

form
:
 Alien Dictionary problem in dsa

Array Pair Sum Divisibility

Problem

DIFFERENCE BETWEEN
GREEDY AND DIVIDE AND
CONQUER

How do you check if a given

array represents a heap

LINKED LIST REVERSE

MAXIMUM SIZE RECTANGLE

Priority queue of pairs in C++

with ordering by first and second
element

Reversing Individual Words and

Unveiling the Secrets of
Histograms In the above tree, we can observe that the double black situation
has been resolved. It also satisfies the properties of the Red Black
Sliding SubArray Beauty
tree.
Two Pointer Technique
Case 5: If double black's sibling is black, sibling's child who is far
UGLY NUMBERS IN DSA
from the double black is black, but near child to double black is
Check for Balanced Brackets in red.
an expression

Largest Number After Digit Swap the color of double black's sibling and the sibling
Swaps By Parity child which is nearer to the double black node.
Minimize Deviation In Array
Rotate the sibling in the opposite direction of the double
Print a given matrix in spiral form black.
Print unique rows in a given
Apply case 6
Boolean matrix

Restrictive Candy Crush Suppose we want to delete the node 1 in the below tree.

Search in a row wise and column

wise sorted matrix

SIP Stack

Stacked Bar Chart

Search Query Auto Complete

Applications of the greedy

algorithm

Applications, Advantages and

Disadvantages of Arrays

Applications, Advantages and

Disadvantages of Queue

Applications, Advantages and

Disadvantages of Stacks

Floor and Ceil from a BST

First, we replace the value 1 with the nil value. The node becomes
India Stack double black as both the nodes, i.e., 1 and nil are black. It satisfies
the case 3 that implies if DB's sibling is black and both its
children are black. First, we remove the double black of the nil
:
 Next Higher Palindromic node. Since the parent of DB is Black, so when the black color is
Numbers using the Same Set of added to the parent node then it becomes double black. After
Digits adding the color, the double black's sibling color changes to Red
QuickSort on Singly Linked List as shown below.

Reverse a Number using Stacks

Serialize and Deserialize an N-ary

Tree

Stack Pointer

What is a K-connected Graph

Append K Integers with Minimal

Sum Problem

Circular Linked Lists Introduction

and Application

Detect cycle in an undirected

graph in C++

Detect Cycle in Graph using DSU

We can observe in the above screenshot that the double black
Find the maximum number of
problem still exists in the tree. So, we will reapply the cases. We will
marked indices problem
apply case 5 because the sibling of node 5 is node 30, which is
Generalized Suffix Tree black in color, the child of node 30, which is far from node 5 is
Interval Tree black, and the child of the node 30 which is near to node 5 is Red.
In this case, first we will swap the color of node 30 and node 25 so
Maximum Number of Tasks
Assignment Problem the color of node 30 changes to Red and the color of node 25
changes to Black as shown below.
Merge K Sorted Lists

Triplet sum closest to given

number

Apply Operations To Maximize

Frequency Score

Difference between malloc and

realloc

Merge Sort on Singly Linked Lists

Minimum Number Of Frogs

Croaking

Total Distance Travelled

X Of A Kind In A Deck Of Cards

Applications, Advantages and

Disadvantages of Linked List
Once the swapping of the color between the nodes is completed,
Balls rolling in the maze
we need to rotate the sibling in the opposite direction of the
Destroy Sequential Targets
double black node. In this rotation, the node 30 moves downwards
Difference Between Push and while the node 25 moves upwards as shown below.
Pop in Stack

Dynamic Programming (DP) on

Grids

Find all good strings problem in

Data Structure
:
 Find Itinerary from a given list of
tickets

Height of n-ary tree if parent

array is given

Maximum Deletions on a String

Reversal algorithm for Array

rotation

Reverse Pairs Problem in Data

Structure

String Hashing using the

Polynomial Rolling Hash
Function

The Great Tree-List Recursion As we can observe in the above tree that double black situation
Problem still exists. So, we need to case 6. Let's first see what is case 6.

Trapping of rainwater problem in

Case 6: If double black's sibling is black, far child is Red
Data Structure

What Does Big O(N^2) Swap the color of Parent and its sibling node.
Complexity Mean
Rotate the parent towards the Double black's direction
How to handle duplicates in
Binary Search Tree
Remove Double black
Optimal cell in matrix to collect
maximum coins Change the Red color to black.

Maximizing Chocolates in Grid

Now we will apply case 6 in the above example to solve the double
using 2 robots
black's situation.
Create a matrix with alternating
rectangles of O and X In the above example, the double black is node 5, and the sibling

Interleave the first half of the of node 5 is node 25, which is black in color. The far child of the
queue with the second half double black node is node 30, which is Red in color as shown in
the below figure:
The sum of all elements between
k1'th and k2'th smallest elements

Binary Indexed Tree Range

Updates and Point Queries

Burn the binary tree starting

from the target node

Check Matrix Transformation by

Flipping Sub-Matrices along the
Principal or Anti-Diagonal

DFS for an n-ary Tree(Acyclic

Graph) Represented as an
Adjacency List

Difference Between Counting

Sort and Bucket Sort

Internal Data Structures and First, we will swap the colors of Parent and its sibling. The parent of
Time Complexity Table of All the node 5 is node 10, and the sibling node is node 25. The colors of
C++ STL Containers both the nodes are black, so there is no swapping would occur.

K Centres Problem (Greedy

In the second step, we need to rotate the parent in the double
Approximate Algorithm)
black's direction. After rotation, node 25 will move upwards,
whereas node 10 will move downwards. Once the rotation is
:
 Left Rotation and Right Rotation performed, the tree would like, as shown in the below figure:
of a String

Merge Two Sorted Linked Lists

Move all Zeroes to End of Array

Number of flips to make binary

string alternate

Program to Reveal the Positions

in Minesweeper

Tarjan's Algorithm to Find

Strongly Connected
Components

Difference between big o and

big theta ? and big omega ?
notations
In the next step, we will remove double black from node 5 and
node 5 will give its black color to the far child, i.e., node 30.
Therefore, the color of node 30 changes to black as shown in the
DS MCQ below figure.

Data Structure MCQ

Advanced DS MCQ

Singly Linked List

Insertion at beginning

Insertion at end

Insertion after specified node

Deletion at beginning

Deletion at end Now let us implement the Red-black tree Data Structure in the
java programming language.
Deletion after specified node

Traversing Java Code:

Searching
/*
* A sample Java Program to Implement the Red-
Black Tree Data Structure
Doubly Linked List */
// The Scanner class from the util is imported to take input fr
Insertion at beginning om the user

Insertion at end import java.util.Scanner;

Insertion after specified node

Deletion at beginning // A class named Node_Red_Black_Tree is created whose ea

Deletion at end ch object will work as a Node of the Red-Black Tree
class Node_Red_Black_Tree
Deletion of node having given
{
data

Traversing
// Each element of the Red Black tree node has four mem
:
 Searching bers.
// Out of these four members two variables are of Node_Re
d_Black_Tree class type named left_node_addr and right_no
de_addr storing the left and right nodes of the previous nod
Circular Linked List
e
Node_Red_Black_Tree left_node_addr, right_node_addr;
Insertion at beginning
// The node_data Integer variable is used to store the data
Insertion at end present in that particular node
int node_data;
Deletion at beginning
// The node_data Integer variable is used to store the color
Deletion at the end
of that particular node
int colour_of_node;

Circular Doubly List /* Constructor of Node_Red_Black_Tree class */

public Node_Red_Black_Tree(int thenode_data)
Insertion at beginning {
this( thenode_data, null, null );
Insertion at end
}
Deletion at beginning /* Constructor of Node_Red_Black_Tree class */
Deletion at the end public Node_Red_Black_Tree(int thenode_data, Node_Re
d_Black_Tree lt, Node_Red_Black_Tree rt)
{
left_node_addr = lt;
Binary Tree
right_node_addr = rt;
node_data = thenode_data;
Pre-order Traversal
colour_of_node = 1;
In-order Traversal }
}
Post-order Traversal

// A class named Node_Red_Black_Tree is created whose ea

ch object will work as the Red-Black Tree
Binary Search Tree class Red_Black_Tree
{
Searching in BST private Node_Red_Black_Tree current_node;
Insertion in BST private Node_Red_Black_Tree parent_node;
private Node_Red_Black_Tree grand_node;
Deletion in BST
private Node_Red_Black_Tree great_node;
private Node_Red_Black_Tree header_node;
private static Node_Red_Black_Tree node_null;
AVL Tree
/* static block to initialize the data */
Insertion in AVL Tree static
{
a)LL Rotation
node_null = new Node_Red_Black_Tree(0);
b)LR Rotation
node_null.left_node_addr = node_null;
c)RL Rotation node_null.right_node_addr = node_null;

d)RR Rotation
}

Deletion in AVL Tree

// color coding
/* Black - 1 RED - 0 */
:
 static final int BLACK = 1;
static final int RED = 0;

/* Constructor of the Red_Black_Tree class */

public Red_Black_Tree(int negInf)
{
header_node = new Node_Red_Black_Tree(negInf);
header_node.left_node_addr = node_null;
header_node.right_node_addr = node_null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return header_node.right_node_addr == node_null;
}
/* Make the tree logically empty */
public void makeEmpty()
{
header_node.right_node_addr = node_null;
}
/* Function to insert item in the Red_Black_Tree class obje
ct */
public void insert(int item )
{
current_node = parent_node = grand_node = header_no
de;
node_null.node_data = item;
while (current_node.node_data != item)
{
great_node = grand_node;
grand_node = parent_node;
parent_node = current_node;
current_node = item < current_node.node_data ? curr
ent_node.left_node_addr : current_node.right_node_addr;
// Check if two red children and fix if so
if (current_node.left_node_addr.colour_of_node == RE
D && current_node.right_node_addr.colour_of_node == RED)

handleReorient( item );
}
// Insertion fails if already present
if (current_node != node_null)
return;
current_node = new Node_Red_Black_Tree(item, node_
null, node_null);
// Attach to parent_node
if (item < parent_node.node_data)
parent_node.left_node_addr = current_node;
else
parent_node.right_node_addr = current_node;
:
 handleReorient( item );
}
private void handleReorient(int item)
{
// Do the colour_of_node flip
current_node.colour_of_node = RED;
current_node.left_node_addr.colour_of_node = BLACK;
current_node.right_node_addr.colour_of_node = BLACK
;

if (parent_node.colour_of_node == RED)
{
// Have to rotate
grand_node.colour_of_node = RED;
if (item < grand_node.node_data != item < parent_nod
e.node_data)
parent_node = rotate( item, grand_node ); // Start d
bl rotate
current_node = rotate(item, great_node );
current_node.colour_of_node = BLACK;
}
// Make root black
header_node.right_node_addr.colour_of_node = BLACK;

}
private Node_Red_Black_Tree rotate(int item, Node_Red_
Black_Tree parent_node)
{
if(item < parent_node.node_data)
return parent_node.left_node_addr = item < parent_n
ode.left_node_addr.node_data ? rotateWithleft_node_addrC
hild(parent_node.left_node_addr) : rotateWithright_node_ad
drChild(parent_node.left_node_addr) ;
else
return parent_node.right_node_addr = item < parent
_node.right_node_addr.node_data ? rotateWithleft_node_ad
drChild(parent_node.right_node_addr) : rotateWithright_no
de_addrChild(parent_node.right_node_addr);
}
/* Rotate binary tree node with left_node_addr child */
private Node_Red_Black_Tree rotateWithleft_node_addr
Child(Node_Red_Black_Tree k2)
{
Node_Red_Black_Tree k1 = k2.left_node_addr;
k2.left_node_addr = k1.right_node_addr;
k1.right_node_addr = k2;
return k1;
}
/* Rotate binary tree node with right_node_addr child */
private Node_Red_Black_Tree rotateWithright_node_add
:
 rChild(Node_Red_Black_Tree k1)
{
Node_Red_Black_Tree k2 = k1.right_node_addr;
k1.right_node_addr = k2.left_node_addr;
k2.left_node_addr = k1;
return k2;
}

/* Functions to count number of nodes */

public int countNodes()
{
return countNodes(header_node.right_node_addr);
}
private int countNodes(Node_Red_Black_Tree r)
{
if (r == node_null)
return 0;
else
{
int l = 1;
l += countNodes(r.left_node_addr);
l += countNodes(r.right_node_addr);
return l;
}
}
/* Functions to search for an node_data */
public boolean search(int val)
{
return search(header_node.right_node_addr, val);
}
private boolean search(Node_Red_Black_Tree r, int val)
{
boolean found = false;
while ((r != node_null) && !found)
{
int rval = r.node_data;
if (val < rval)
r = r.left_node_addr;
else if (val > rval)
r = r.right_node_addr;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for in order traversal of the Red_Black_Tree cla
:
 ss object*/
public void inorder()
{
inorder(header_node.right_node_addr);
}
private void inorder(Node_Red_Black_Tree r)
{
if (r != node_null)
{
inorder(r.left_node_addr);
char c = 'B';
if (r.colour_of_node == 0)
c = 'R';
System.out.print(r.node_data +""+c+" ");
inorder(r.right_node_addr);
}
}
/* Function for pre-
order traversal of the Red_Black_Tree class object*/
public void preorder()
{
preorder(header_node.right_node_addr);
}
private void preorder(Node_Red_Black_Tree r)
{
if (r != node_null)
{
char c = 'B';
if (r.colour_of_node == 0)
c = 'R';
System.out.print(r.node_data +""+c+" ");
preorder(r.left_node_addr);
preorder(r.right_node_addr);
}
}
/* Function for post-
order traversal of the Red_Black_Tree class object*/
public void postorder()
{
postorder(header_node.right_node_addr);
}
private void postorder(Node_Red_Black_Tree r)
{
if (r != node_null)
{
postorder(r.left_node_addr);
postorder(r.right_node_addr);
char c = 'B';
if (r.colour_of_node == 0)
c = 'R';
:
 System.out.print(r.node_data +""+c+" ");
}
}
}

/* Class Red_Black_Tree_Run */
class Red_Black_Tree_Run
{
public static void main(String[] args)
{
Scanner scannner_object = new Scanner(System.in);
/* Creating object of RedBlack Tree */
Red_Black_Tree red_black_tree_object = new Red_Black
_Tree(Integer.MIN_VALUE);
System.out.println("Red Black Tree Test\n");
char ch;
/* Perform tree operations */
do
{
System.out.println("\nThe options list for Red Black Tr
ee::\n");
System.out.println("1. To add a new node in the Red-
Black Tree");
System.out.println("2. To search the Red-
Black Tree for a node");
System.out.println("3. To get node count of nodes in R
ed Black Tree");
System.out.println("4. To check if the Red_Black_Tree i
s Empty or not?");
System.out.println("5. To Clear the Red_Black_Tree.");

int option_list_choice = scannner_object.nextInt();

switch (option_list_choice)
{
case 1 :
System.out.println("Enter integer node_data to inser
t");
red_black_tree_object.insert( scannner_object.nextI
nt() );
break;
case 2 :
System.out.println("Enter integer node_data to sear
ch");
System.out.println("Search result : "+ red_black_tree
_object.search( scannner_object.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ red_black_tree_objec
t.countNodes());
:
 break;
case 4 :
System.out.println("Empty status = "+ red_black_tre
e_object.isEmpty());
break;
case 5 :
System.out.println("\nTree Cleared");
red_black_tree_object.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}

System.out.print("\nRBT in Post-order: ");

red_black_tree_object.postorder();
System.out.print("\nRBT in Pre-order: ");
red_black_tree_object.preorder();
System.out.print("\nRBT in In-order: ");
red_black_tree_object.inorder();

System.out.println("\nWanna proceed further(Type y o

r n)? \n");
ch = scannner_object.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Output:

Red Black Tree Test

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
10

RBT in Post-order: 10B

RBT in Pre-order: 10B
RBT in In-order: 10B
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

:
 1. To add a new node in the Red-Black Tree
2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
18

RBT in Post-order: 18R 10B

RBT in Pre-order: 10B 18R
RBT in In-order: 10B 18R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
45

RBT in Post-order: 10R 45R 18B

RBT in Pre-order: 18B 10R 45R
RBT in In-order: 10R 18B 45R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
33

RBT in Post-order: 10B 33R 45B 18B

RBT in Pre-order: 18B 10B 45B 33R
RBT in In-order: 10B 18B 33R 45B
Wanna proceed further(Type y or n)?
:
 y

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
87

RBT in Post-order: 10B 33R 87R 45B 18B

RBT in Pre-order: 18B 10B 45B 33R 87R
RBT in In-order: 10B 18B 33R 45B 87R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
90

RBT in Post-order: 10B 33B 90R 87B 45R 18B

RBT in Pre-order: 18B 10B 45R 33B 87B 90R
RBT in In-order: 10B 18B 33B 45R 87B 90R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
31
:
 RBT in Post-order: 10B 31R 33B 90R 87B 45R 18B
RBT in Pre-order: 18B 10B 45R 33B 31R 87B 90R
RBT in In-order: 10B 18B 31R 33B 45R 87B 90R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
1
Enter integer node_data to insert
77

RBT in Post-order: 10B 31R 33B 77R 90R 87B 45R 18B
RBT in Pre-order: 18B 10B 45R 33B 31R 87B 77R 90R
RBT in In-order: 10B 18B 31R 33B 45R 77R 87B 90R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
2
Enter integer node_data to search
18
Search result: true

RBT in Post-order: 10B 31R 33B 77R 90R 87B 45R 18B
RBT in Pre-order: 18B 10B 45R 33B 31R 87B 77R 90R
RBT in In-order: 10B 18B 31R 33B 45R 77R 87B 90R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
:
 5. To Clear the Red_Black_Tree.
3
Nodes = 8

RBT in Post-order: 10B 31R 33B 77R 90R 87B 45R 18B
RBT in Pre-order: 18B 10B 45R 33B 31R 87B 77R 90R
RBT in In-order: 10B 18B 31R 33B 45R 77R 87B 90R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
4
Empty status = false

RBT in Post-order: 10B 31R 33B 77R 90R 87B 45R 18B
RBT in Pre-order: 18B 10B 45R 33B 31R 87B 77R 90R
RBT in In-order: 10B 18B 31R 33B 45R 77R 87B 90R
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
5

Tree Cleared

RBT in Post-order:
RBT in Pre-order:
RBT in In-order:
Wanna proceed further(Type y or n)?

The options list for Red Black Tree::

1. To add a new node in the Red-Black Tree

2. To search the Red-Black Tree for a node
:
 3. To get node count of nodes in Red Black Tree
4. To check if the Red_Black_Tree is Empty or not?
5. To Clear the Red_Black_Tree.
4
Empty status = true

RBT in Post-order:
RBT in Pre-order:
RBT in In-order:
Wanna proceed further(Type y or n)?

Now let us see a code in C++ language to implement RBT data

structure.

C++ Code:

#include<iostream>

using namespace std;

struct node_of_the_red_black_tree
{
int key;
node_of_the_red_black_tree *parent;
char color;
node_of_the_red_black_tree *left;
node_of_the_red_black_tree *right;
};
class Red_Black_Tree
{
node_of_the_red_black_tree *root;
node_of_the_red_black_tree *temp_node1;
public :
Red_Black_Tree()
{
temp_node1=NULL;
root=NULL;
}
void insert_a_node_to_rbt();
void insert_a_node_to_rbtfix(node_of_the_red_black_tree
*);
void leftrotate_rbt_node(node_of_the_red_black_tree *);
void rightrotate_rbt_node(node_of_the_red_black_tree *);

void del_rbt_node();
node_of_the_red_black_tree* successor(node_of_the_red_
black_tree *);
void del_rbt_nodefix(node_of_the_red_black_tree *);
:
 void disp();
void display( node_of_the_red_black_tree *);
void search_rbt_node();
};
void Red_Black_Tree::insert_a_node_to_rbt()
{
int init_value,i=0;
cout<<"\nKey value for the node_of_the_red_black_tree to
insert_a_node_to_rbt in RBT: "; cin>>init_value;
node_of_the_red_black_tree *temp_node,*temp_node1;
node_of_the_red_black_tree *t=new node_of_the_red_bla
ck_tree;
t->key=init_value;
t->left=NULL;
t->right=NULL;
t->color='r';
temp_node=root;
temp_node1=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(temp_node!=NULL)
{
temp_node1=temp_node;
if(temp_node->key<t->key)
temp_node=temp_node->right;
else
temp_node=temp_node->left;
}
t->parent=temp_node1;
if(temp_node1->key<t->key)
temp_node1->right=t;
else
temp_node1->left=t;
}
insert_a_node_to_rbtfix(t);
}
void Red_Black_Tree::insert_a_node_to_rbtfix(node_of_the_r
ed_black_tree *t)
{
node_of_the_red_black_tree *u;
if(root==t)
{
t->color='b';
return;
}
:
 while(t->parent!=NULL&&t->parent->color=='r')
{
node_of_the_red_black_tree *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate_rbt_node(t);
}
t->parent->color='b';
g->color='r';
rightrotate_rbt_node(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate_rbt_node(t);
}
t->parent->color='b';
g->color='r';
:
 leftrotate_rbt_node(g);
}
}
root->color='b';
}
}

void Red_Black_Tree::del_rbt_node()
{
if(root==NULL)
{
cout<<"\nEmpty Tree." ;
return ;
}
int x;
cout<<"\nEnter the key of the node_of_the_red_black_tree
to be del_rbt_nodeeted: "; cin>>x;
node_of_the_red_black_tree *temp_node;
temp_node=root;
node_of_the_red_black_tree *y=NULL;
node_of_the_red_black_tree *temp_node1=NULL;
int found=0;
while(temp_node!=NULL&&found==0)
{
if(temp_node->key==x)
found=1;
if(found==0)
{
if(temp_node->key<x) temp_node=temp_node-
>right;
else
temp_node=temp_node->left;
}
}
if(found==0)
{
cout<<"\nElement Not Found.";
return ;
}
else
{
cout<<"\ndel_rbt_nodeeted Element: "<<temp_node-
>key;
cout<<"\nColour: "; if(temp_node->color=='b')
cout<<"Black\n";
else
cout<<"Red\n"; if(temp_node->parent!=NULL)
cout<<"\nParent: "<<temp_node->parent->key;
else
cout<<"\nno parent node_of_the_red_black_tree pre
:
 sent "; if(temp_node->right!=NULL)
cout<<"\nRight Child: "<<temp_node->right->key;
else
cout<<"\nno right child node_of_the_red_black_tree
present. "; if(temp_node->left!=NULL)
cout<<"\nLeft Child: "<<temp_node->left->key;
else
cout<<"\nno left child node_of_the_red_black_tree p
resent. ";
cout<<"\nnode_of_the_red_black_tree del_rbt_nodeete
d."; if(temp_node->left==NULL||temp_node->right==NULL)
y=temp_node;
else
y=successor(temp_node);
if(y->left!=NULL)
temp_node1=y->left;
else
{
if(y->right!=NULL)
temp_node1=y->right;
else
temp_node1=NULL;
}
if(temp_node1!=NULL)
temp_node1->parent=y->parent;
if(y->parent==NULL)
root=temp_node1;
else
{
if(y==y->parent->left)
y->parent->left=temp_node1;
else
y->parent->right=temp_node1;
}
if(y!=temp_node)
{
temp_node->color=y->color;
temp_node->key=y->key;
}
if(y->color=='b')
del_rbt_nodefix(temp_node1);
}
}

void Red_Black_Tree::del_rbt_nodefix(node_of_the_red_blac
k_tree *temp_node)
{
node_of_the_red_black_tree *s;
while(temp_node!=root&&temp_node->color=='b')
{
:
 if(temp_node->parent->left==temp_node)
{
s=temp_node->parent->right;
if(s->color=='r')
{
s->color='b';
temp_node->parent->color='r';
leftrotate_rbt_node(temp_node->parent);
s=temp_node->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
temp_node=temp_node->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate_rbt_node(s);
s=temp_node->parent->right;
}
s->color=temp_node->parent->color;
temp_node->parent->color='b';
s->right->color='b';
leftrotate_rbt_node(temp_node->parent);
temp_node=root;
}
}
else
{
s=temp_node->parent->left;
if(s->color=='r')
{
s->color='b';
temp_node->parent->color='r';
rightrotate_rbt_node(temp_node->parent);
s=temp_node->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
temp_node=temp_node->parent;
}
else
{
if(s->left->color=='b')
{
:
 s->right->color='b';
s->color='r';
leftrotate_rbt_node(s);
s=temp_node->parent->left;
}
s->color=temp_node->parent->color;
temp_node->parent->color='b';
s->left->color='b';
rightrotate_rbt_node(temp_node->parent);
temp_node=root;
}
}
temp_node->color='b';
root->color='b';
}
}

void Red_Black_Tree::leftrotate_rbt_node(node_of_the_red_
black_tree *temp_node)
{
if(temp_node->right==NULL)
return ;
else
{
node_of_the_red_black_tree *y=temp_node->right;
if(y->left!=NULL)
{
temp_node->right=y->left;
y->left->parent=temp_node;
}
else
temp_node->right=NULL;
if(temp_node->parent!=NULL)
y->parent=temp_node->parent;
if(temp_node->parent==NULL)
root=y;
else
{
if(temp_node==temp_node->parent->left)
temp_node->parent->left=y;
else
temp_node->parent->right=y;
}
y->left=temp_node;
temp_node->parent=y;
}
}
void Red_Black_Tree::rightrotate_rbt_node(node_of_the_red
_black_tree *temp_node)
{
:
 if(temp_node->left==NULL)
return ;
else
{
node_of_the_red_black_tree *y=temp_node->left;
if(y->right!=NULL)
{
temp_node->left=y->right;
y->right->parent=temp_node;
}
else
temp_node->left=NULL;
if(temp_node->parent!=NULL)
y->parent=temp_node->parent;
if(temp_node->parent==NULL)
root=y;
else
{
if(temp_node==temp_node->parent->left)
temp_node->parent->left=y;
else
temp_node->parent->right=y;
}
y->right=temp_node;
temp_node->parent=y;
}
}

node_of_the_red_black_tree* Red_Black_Tree::successor(nod
e_of_the_red_black_tree *temp_node)
{
node_of_the_red_black_tree *y=NULL;
if(temp_node->left!=NULL)
{
y=temp_node->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=temp_node->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}

void Red_Black_Tree::disp()
{
display(root);
:
 }
void Red_Black_Tree::display(node_of_the_red_black_tree *t
emp_node)
{
if(root==NULL)
{
cout<<"\nEmpty Tree.";
return ;
}
if(temp_node!=NULL)
{
cout<<"\n\t node_of_the_red_black_tree: ";
cout<<"\n Key: "<<temp_node->key;
cout<<"\n Colour: "; if(temp_node->color=='b')
cout<<"Black";
else
cout<<"Red"; if(temp_node->parent!=NULL)
cout<<"\n Parent: "<<temp_node->parent->key;
else
cout<<"\n no parent node_of_the_red_black_tre
e present "; if(temp_node->right!=NULL)
cout<<"\n Right Child: "<<temp_node->right-
>key;
else
cout<<"\n no right child node_of_the_red_black_
tree present. "; if(temp_node->left!=NULL)
cout<<"\n Left Child: "<<temp_node->left->key;
else
cout<<"\n no left child node_of_the_red_black_tr
ee present. ";
cout<<endl; if(temp_node->left)
{
cout<<"\n\nLeft:\n"; display(temp_node->left);
}
/*else
cout<<"\nNo Left Child.\n";*/ if(temp_node->right)
{
cout<<"\n\nRight:\n"; display(temp_node->right);
}
/*else
cout<<"\nNo Right Child.\n"*/
}
}
void Red_Black_Tree::search_rbt_node()
{
if(root==NULL)
{
cout<<"\nEmpty Tree\n" ;
return ;
}
:
 int x;
cout<<"\n Enter key of the node_of_the_red_black_tree to
be search_rbt_nodeed: "; cin>>x;
node_of_the_red_black_tree *temp_node=root;
int found=0;
while(temp_node!=NULL&& found==0)
{
if(temp_node->key==x)
found=1;
if(found==0)
{
if(temp_node->key<x) temp_node=temp_node-
>right;
else
temp_node=temp_node->left;
}
}
if(found==0)
cout<<"\nElement Not Found.";
else
{
cout<<"\n\t FOUND node_of_the_red_black_tree: ";
cout<<"\n Key: "<<temp_node->key;
cout<<"\n Colour: "; if(temp_node->color=='b')
cout<<"Black";
else
cout<<"Red"; if(temp_node->parent!=NULL)
cout<<"\n Parent: "<<temp_node->parent->key;
else
cout<<"\n no parent node_of_the_red_black_tre
e present"; if(temp_node->right!=NULL)
cout<<"\n Right Child: "<<temp_node->right-
>key;
else
cout<<"\n no right child node_of_the_red_black_
tree present. "; if(temp_node->left!=NULL)
cout<<"\n Left Child: "<<temp_node->left->key;
else
cout<<"\n no left child node_of_the_red_black_tr
ee present";
cout<<endl;

}
}
int main()
{
int ch,y=0;
Red_Black_Tree obj;
do
{
:
 cout<<"\nThe options list for Red Black Tree::" ;
cout<<"\n1. To add a new node_of_the_red_black_tre
e in the Red-Black Tree";
cout<<"\n2. To search_rbt_node the Red-
Black Tree for a node_of_the_red_black_tree";
cout<<"\n3. To del_rbt_nodeete an existing Red-
Black tree node_of_the_red_black_tree";
cout<<"\n4. To display all the node_of_the_red_black
_trees of the Red-Black Tree ";
cout<<"\n5. To exit the code execution." ;
cout<<"\nInput: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert_a_node_to_rbt();
cout<<"\nNew node_of_the_red_black_tre
e added.\n";
break;
case 2 :
obj.search_rbt_node();
break;
case 3 :

obj.del_rbt_node();
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<"\nEnter a Valid Choice.";
}
cout<<endl;

}while(y!=1);
return 0;
}

Output:
:
 The options list for Red Black Tree::
1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 1

Key value for the node_of_the_red_black_tree to

insert_a_node_to_rbt in RBT: 12

New node_of_the_red_black_tree added.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 1

Key value for the node_of_the_red_black_tree to

insert_a_node_to_rbt in RBT: 45

New node_of_the_red_black_tree added.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 1

Key value for the node_of_the_red_black_tree to

insert_a_node_to_rbt in RBT: 23
:
 New node_of_the_red_black_tree added.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 1

Key value for the node_of_the_red_black_tree to

insert_a_node_to_rbt in RBT: 98

New node_of_the_red_black_tree added.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 4

node_of_the_red_black_tree:
Key: 23
Colour: Black
Parent: 12
Right Child: 45
Left Child: 12

Left:

node_of_the_red_black_tree:
Key: 12
Colour: Black
Parent: 23
no right child node_of_the_red_black_tree present.
no left child node_of_the_red_black_tree present.
:
 Right:

node_of_the_red_black_tree:
Key: 45
Colour: Black
Parent: 23
Right Child: 98
no left child node_of_the_red_black_tree present.

Right:

node_of_the_red_black_tree:
Key: 98
Colour: Red
Parent: 45
no right child node_of_the_red_black_tree present.
no left child node_of_the_red_black_tree present.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 2

Enter key of the node_of_the_red_black_tree to be

search_rbt_nodeed: 98

FOUND node_of_the_red_black_tree:
Key: 98
Colour: Red
Parent: 45
no right child node_of_the_red_black_tree present.
no left child node_of_the_red_black_tree present

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
:
 3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 3

Enter the key of the node_of_the_red_black_tree to be

del_rbt_nodeeted: 45

del_rbt_nodeeted Element: 45
Colour: Black

Parent: 23
Right Child: 98
no left child node_of_the_red_black_tree present.
node_of_the_red_black_tree del_rbt_nodeeted.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 4

node_of_the_red_black_tree:
Key: 23
Colour: Black
Parent: 12
Right Child: 98
Left Child: 12

Left:

node_of_the_red_black_tree:
Key: 12
Colour: Black
Parent: 23
no right child node_of_the_red_black_tree present.
no left child node_of_the_red_black_tree present.

Right:
:
 node_of_the_red_black_tree:
Key: 98
Colour: Red
Parent: 23
no right child node_of_the_red_black_tree present.
no left child node_of_the_red_black_tree present.

The options list for Red Black Tree::

1. To add a new node_of_the_red_black_tree in the Red-
Black Tree
2. To search_rbt_node the Red-Black Tree for a
node_of_the_red_black_tree
3. To del_rbt_nodeete an existing Red-Black tree
node_of_the_red_black_tree
4. To display all the node_of_the_red_black_trees of
the Red-Black Tree
5. To exit the code execution.
Input: 5

Next Topic DS Graph

← prev next →
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
 Latest Courses  
:
: