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.
  • First add the add root to the 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:

DFS

Read more

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).

Read more

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.

Read more

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:

Read more

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;
	}
}

Read more

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.

Input: A Linked List

Output: Reversed Linked List

Example:

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

Approach:

Read more

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

Input: A Linked List and access to the node which needs to be deleted

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

Read more

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:

Read more

Remove Duplicates from an Unsorted Linked list

Objective: Write a program to remove the duplicates from an unsorted linked list

Example:

Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3

Input: An unsorted linked list

Output: Linked list with no duplicates.

Approach:

  • Create a Hash Map
  • Take two pointers, prevNode and CurrNode.
  • PrevNode will point to the head of the linked list and currNode will point to the head.next.

Read more