Find the Deepest Node in a Binary Tree.

Objective: – Given a binary tree, write an algorithm to Find the deepest node in it.

Approach:

  • Take two global variable as “deepestlevel” and “value“.
  • starting with level=0, Do the inorder traversal and whenever you go down one level ( root.left OR root.right), increase the level by 1.
  • Keep checking if deepestlevel < level, if yes then update the “deepestlevel ” and “value “.
  • At the end return “value“, which will the deepest node value.
  • See the code for better explanation.

Read more

Track the Maximum Element in a Stack.

Objective: In a Stack, keep track of maximum value in it. It might be the top element in the stack but once it is poped out, the maximum value should be from the rest of the elements in the stack.

Approach:

  • Create another another Stack(call it as track) which will keep track of maximum in the given Stack(call it as main).
  • When you insert an element in the main stack for the first time ( means it is empty), insert it in the track Stack as well.
  • Now onwards when you insert a new element(say it is x) in the main Stack, peek() the element from the track Stack ( say it is ‘a‘). Compare x and a and which ever is greater, insert it into track Stack.
  • When you pop the element from the main stack, pop from the track Stack as well
  • So to get to know the maximum element in the main Stack, peek the element in the track Stack. . See Example below.

Thanks Gaurav Dey for suggesting this solution.

Read more

Implement Queue Using Stacks

Objective: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out). Here our objective is to implement queue using stacks. Approach: Take 2 Stacks, stack1 and stack2. stack1 will be used a back of the Queue and stack2 will be used as front of the Queue. Push() operation will be done on … Read more

Merge Sort in a Linked list

Objective: Given a Linked List, Sort it using merge sort. Example: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Reference : Merge Sort in array As it Merge sort, we apply the same logic , Divide and Conquer. Find the length of the link list, say it is L. mid will be L/2. Now we need to divide … Read more

In an Array, find the Smallest Subarray with Sum Greater than the Given Value

Objective: Given an array and an integer, find the smallest subarray whose sum is greater than the given integer.

Examples:

arrA[] = { 1, 5, 20, 70, 8}
Integer = 97
Output : Min Length = 3 Subarray = [20, 70, 8]

 
arrA[] = { 1, 10, 3, 40, 18}
Integer = 50
Output : Min Length = 2 Subarray = [40, 18]

Approach:

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

Read more

Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

Objective: Given an array arrA[], find the maximum j – i such that arr[j] > arr[i]. Example: int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 }; Output: Max(j-i) where j>i and A[j]>A[i] is : 7 Approach: Create 2 Auxilary Arrays say Lmin[] and Rmax[] of the same size as … Read more