Find the number of occurrences of a number in a given sorted array.

Objective: Given a sorted(ascending order) arrays of integers, find out the number of occurences of a number in that array

Input: A sorted array arrA[] and a number x.

Output: number of occurrences of ‘x’ in array arrA[].

Examples :

Array - {1,2,2,2,2,2,2,2,3,4,5,5,6}
x = 2
Output : No of Occurrences of number 2 is 7


Approach:

Read more

Find the first repeated element in an array by its index

Objective: Given an array of integers, find out the first repeated element. First repeated element means the element occurs atleast twice and has smallest index.

Input: An Array

Output: The first repeated element

Examples :

Array {1,1,3,4,6,7,9} first repeated Number : 1
Array {7,2,2,3,7} first repeated Number : 7
Array {5,3,3,3,3,3,3,3,4,4,4,5,3} first repeated Number : 5

Read more

Determine whether given binary tree is binary search tree(BST) or not

Objective: Given a Binary tree, find out whether it’s a binary search tree or not.

Input: A Binary Tree.

Output: True or false based on whether the tree is BST or not.

Approach:

Method 1: If the tree doesn’t have duplicates

  • Do the inorder traversal of the given binary tree.
  • check if the previously visited node is less than the current node value.
  • If yes, then return true
  • Else return false.

The above method works only when the tree doesn’t have any duplicates. (we can choose that either duplicate will either go to the left OR on the right but we cannot choose it randomly while constructing the tree, we need to decide before we construct the tree and it has to be consistent through out and here we are deciding that duplicates should go to the left subtree.) see figure,

Read more

Given two binary trees, check if one binary tree is a subtree of another

Objective: Given two binary trees, check if one binary tree is a subtree of another

Input: Two binary trees

Output: True or false based on whether one tree is subtree of another

Example:

Tree is subtree of another tree example
Tree is subtree of another tree example

Approach:

We know that to indentity any binary tree can be represented as the combination of either inorder and preorder traversal OR inorder and postorder traversal OR inorder and Level order traversal.

Read more

Print a path from Root to Node in Binary Tree

Objective: Given a Binary tree (Not binary Search Tree ), Print a path from root to a given node.

Input: A binary tree, a node x

Output: Path from root to a given node

Example :

path from root to Node example

Approach :

since it’s not a binary search tree, we cannot use binary search technique to reach to the node. we need to travel all the nodes in order to find the node

Read more

Inorder Successor in Binary Tree

Algorithms – Inorder Successor in Binary Tree

Objective: Given a Binary tree (Not a Binary Search Tree ), find the inorder successor of a node.

What is Inorder Successor: Inorder successor of a node is the next node in the inorder traversal of the tree. For the last node in a tree, inorder successor will be NULL

Similar Problems :
Inorder Successor in Binary Search Tree with parent link
Inorder Successor in Binary Search Tree without parent link

Input: A binary tree, a node x

Output: Inorder successor of node x.

Example:

InOrder Successor in binary tree example
InOrder Successor in binary tree example

Approach:

NOTE: since it’s not a binary search tree, we cannot use binary search technique to reach to the node. we need to travel all the nodes in order to find the node for which we need to find the inorder successor.

Read more

Sorted Array to Binary Search Tree of Minimal Height

Objective: Given a sorted array with unique elements, Create a binary search tree with minimal height.

Why minimal height is important :

We can do the linear scan to the array and make the first element as root and insert all other elements into the tree but in that case tree will be skewed , which means all the nodes of the tree will be on the one side of the root so the height of the tree will be equal to the number of elements in the array. So here our objective is to keep the tree balanced as much as possible.

What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one. To read more about balanced tree, click here

Input: A one dimensional array

Output: Binary Search Tree of Minimal Height

Example:

Read more

Level Order Traversal, Print each level in separate line.

Objective: Given a Binary tree , Print each level of a tree in separate line.

NOTE : This problem is very similar ” Create Linked Lists of all the nodes at each depth “

Input: A binary tree

Output: Each level of binary tree, in one line

Example:

Read more

Find whether a Given Binary Tree is Balanced?

Objective: Given a binary tree, Find whether if a Given Binary Tree is Balanced?

What is a balanced Tree: A balanced tree is a tree in which the difference between the heights of sub-trees of any node in the tree is not greater than one.

Input: A Binary Tree

Output: True and false based on whether the tree is balanced or not.

Example:

Balanced Tree Example

Approach :

Naive Approach:
for each node of the tree, get the height of the left subtree and right subtree and check the difference, if it is greater than 1, return false.

Read more

Add two numbers represented by a linked list, Numbers are Stored in FORWARD order

This post is the extension of   – Two numbers represented by a linked list, Number Stored in REVERSE order

Objective: Two numbers represented by a linked listwhere each node contains single digit. The digits are stored in Forward order, means head is pointing to the last digit of the number.

Input: Two numbers represented by Linked Lists

Output: Addition of two numbers represented by a Linked List.

Example:

First Number : 1007
Second Number : 93
Addition : 1100

Read more

Add two numbers represented by a linked list, Numbers are Stored in REVERSE order

We have similar post – Two numbers represented by a linked list, Number Stored in FORWARD order

Objective: Two numbers represented by a linked list where each node contains single digit. The digits are stored in REVERSE order, means head is pointing to the first digit of the number.

Input: Two numbers represented by Linked Lists

Output: Addition of two numbers represented by a Linked List.

Example:

First Number in REVERSE order: 5957
Second Number in REVERSE order : 59
Addition in REVERSE order : 0967
Actual Result in FORWARD ORDER : 9670

Approach:

Read more

Swap Every Kth Node in a LinkedList

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10

Approach:

Read more

Replace all spaces in a String with ‘%20’

Objective: Write an algorithm to replace all spaces in a given string with ‘%20’. You can consider that string has enough space at the end of the string to hold the extra characters.

Input: A String and the true length of a string

Output: Updated string in which each space is replaced by the ‘%20’

Example:

Input String :

I am Sumit Jain    

Output String : 

I%20am%20Sumit%20Jain

 

Approach:

Read more