## Delete X Nodes After Y Nodes In a Linked List

Objective: Given a Linked List and x and y. Delete x number of nodes after y nodes from the start. Example: ->10->20->30->40->50->60->70->80->90->100->110->120 Deleted 4 Nodes after 5 Nodes ->10->20->30->40->50->100->110->120 Approach: We need two pointers. One pointer at one node prior to the nodes to be deleted. ( Move it by y starting from the head). … Read more

## Depth First Search/Traversal in Binary Tree

Objective: Given a Binary Search Tree, Do the Depth First Search/Traversal .

Appraoch:

• Approach is quite simple, use Stack.
• Pop out an element from Stack and add its right and left children to stack.
• Pop out an element and print it and add its children.
• Repeat the above two steps until the Stack id empty.

Example:  ## Check if Array is Consecutive Integers

Objective: Given a array of unsorted numbers, check if all the numbers in the array are consecutive numbers.

Examples:

```int [] arrA = {21,24,22,26,23,25}; - True
(All the integers are consecutive from 21 to 26)
int [] arrB = {11,10,12,14,13}; - True
(All the integers are consecutive from 10 to 14)
int [] arrC = {11,10,14,13}; - False
(Integers are not consecutive, 12 is missing)```

Approach:

Naive Approach: Sorting . Time Complexity – O(nlogn).

Better Approach: Time Complexity – O(n).

## Find intersection between Two Sorted Arrays.

Objective: Given two sorted arrays, Find intersection point between them.

Examples:

```int[] a = { 1, 2, 3, 6, 8, 10 };
int[] b = { 4, 5, 6, 11, 15, 20 };
Output: Intersection point is : 6
```

Approach:

Naive Approach: Use 2 loops and compare each elements in both array and as soon as you find the intersection point, return it. Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

• Say Arrays are arrA[] and arrB[] and indexes for navigation are x and y respectively.
• Since arrays are sorted, compare the first element of both the arrays.(x=0, y=0)
• If both elements are same, we have our intersection point, return it.
• Else if element of arrA[x] > element of arrB[y], increase the arrB[] index, y++.
• Else if element of arrA[x] < element of arrB[y], increase the arrA[] index, x++.
• If any of the array gets over that means you have not found the intersection point. return -1.

## Given a binary tree, Convert it into its Mirror Tree

Objective: Given a binary tree, Convert it into its Mirror Tree

Mirror Tree: Mirror Tree of a binary tree is where left and right child of every node of given binary tree is interexchanged.

Input: A binary tree.

Example:

Approach:

## Given a binary tree, Print All the Nodes that don’t have Siblings.

Objective: Given a binary tree, Print All the Nodes that don’t have siblings.

Note: sibling node is the node which has the same parent, so you need to print the nodes who is a single child of his parent.

Input: A binary tree.

Example:

Approach:

## Check if Two BST’s are Identical

Objective: Given Two binary Search Trees, Check if both are identical.

Input: Two binary Search Trees

Approach:

## Find all common numbers in given three sorted arrays.

Objective: Given three sorted(ascending order) arrays of integers, find out all the common elements in them.

Input: Three sorted arrays.

Output: All the common elements.

Examples :

```Array A = {1,2,3,4,5,6,7,8,9,10};
Array B = {1,3,5,6,7,8,12};
Array C = {2,3,4,5,8,9};
Common Elements are 3,5,8
```

## Minimum number that cannot be formed by any subset of an array

Objective: Given a sorted array of positive integers, find out the smallest integer which cannot be represented as the sum of any subset of the array

Input: A Sorted Array

Output: The smallest number which cannot be represented as the sum of any subset of the given array

Examples :

```Array {1,1,3,4,6,7,9} smallest Number : 32
Array {1,1,1,1,1} smallest Number : 6
Array {2,3,6,7} smallest Number : 1
Array {1,2,6,7,9} smallest Number : 4
```

Approach:

## Find the Size of the Binary Tree

Objective: Given a Binary tree, Find the size of the tree.

Note : Size of the tree is number of nodes in the tree

Input: A Binary Tree.

Output: Size of the tree.

Example : Approach :

## Find the Maximum Depth OR Height of a Binary Tree

Objective: Given a binary tree, find the height of it

Input: A Binary Tree

Output: Height of a binary tree

Example: Approach:

## Binary Search Tree (BST) Complete Implementation.

Binary Tree : A data structure in which we have nodes containing data and two references to other nodes, one on the left and one on the right.

Binary Tree consist of Nodes

• Nodes are nothing but objects of a class and each node has data and a link to the left node and right node.
• Usually we call the starting node of a tree as root.
```class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
```

## Reverse a Linked List – Part 2

This post is the extension of our earlier post Reverse a linked list. Here We have provided the better recursive solution in which we start reversing the list from the end.

Objective: Reverse the given linked list.

Example:

```Original List :->10->8->6->4->2
Reversed List :->2->4->6->8->10```

Approach:

## Delete a Node in the Middle of a linked list, Given only access to that Node

Objective: Write a program to Delete a Node in the Middle of a linked list, Given only access to that Node

Example:

```Original List : ->1->2->8->3->7->0->4
After Deleting the mid node (say 7) : ->1->2->8->3->0->4
```

Output: Linked list with deleted node

Approach:

• Approach is tricky and simple
• Copy the value of next node to the node which you want to delete
• Delete the next node

## Find the n’th Node from the end of a given Linked List

Objective: Given a linked list and integer ‘n’, write an algorithm to find the nth node from the end in the Linked List.

Example:

```Original List : ->1->2->8->3->7->0->4
Output : 3rd Element from the end is : 7
```

Input: An unsorted linked list and integer k

Output: The kth to Last Element of a Singly Linked List

Approach: