Sort an Given Array in the order defined by another array

Objective: Given an array of integers, write an algorithm to sort it according to the order defined by another array.

Input: An Array of Integers

Example:

Input Array : 2 6 9 1 4 4 2 1 10 13 5 7 8

DefinedArray : 1 2 4 6

Output : 1 1 2 2 4 4 6 5 7 8 9 10 13

Appraoch:

Method 1: Sort and Search

Read moreSort an Given Array in the order defined by another array

Sort an Array – odd numbers appear first in ascending order followed by the even numbers in descending order.

Objective: Given an array of intergers, sort it such that the odd numbers appear first followed by the even numbers . The odd numbers in ascending order and the even numbers in descending order.

Input: An Array of Integers

Example:

Input Array : 1 2 3 4 5 6 7 8 9 10
Output : 1 3 5 7 9 10 8 6 4 2

Read moreSort an Array – odd numbers appear first in ascending order followed by the even numbers in descending order.

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

Read moreFind the number of occurrences of a number in a given sorted array.

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 moreFind the first repeated element in an array by its index

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

Objective: Given a Binary tree, find out whether its binary search tree or not.

Input: A Binary Tree.

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

Approach:

Method 1 : If 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 tree doesn’t have any duplicates.(we can choose that ether duplicates will either go to 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 moreDetermine whether given binary tree is binary search tree(BST) or not

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:

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

Inorder Successor in Binary Tree

Algorithms – Inorder Successor in Binary Tree

Objective: Given a Binary tree (Not 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:

Read moreInorder Successor in Binary Tree

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 moreSorted Array to Binary Search Tree of Minimal Height

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 moreLevel Order Traversal, Print each level in separate line.

Find whether if a Given Binary Tree is Balanced?

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

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.

Input: A Binary Tree

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

Example:

Balanced Tree Example

Approach :

Read moreFind whether if a Given Binary Tree is Balanced?

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 moreAdd two numbers represented by a linked list, Numbers are Stored in FORWARD order