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

Reverse the binary representation of a number.

Objective: Write a program to Reverse the binary representation of a number

Example:

Input : 30
Output : 15

Explanation:

binary representation of 30 is : 11110
reverse of binary representation : 01111
decimal of reversed binary representation is : 15

Input: A Number

Output: Decimal of reversed binary representation of a number.

Approach:

Read moreReverse the binary representation of a number.

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 moreDelete a Node in the Middle of a linked list, Given only access to that 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:

Read moreFind the n’th Node from the end of a given Linked List

Check if one string is Rotation of another string

Objective: Write an algorithm to check if one string is Rotation of another string. This question has been asked in the Amazon interview.

Example:

Input Strings : 'sumitjain' and 'tjainsumi'
Output : true

Input String : 'Jaain' and 'ainJ'
Output: false

Input: Two Strings

Output: True or false based on whether strings are rotation of each other.

Approach:

Read moreCheck if one string is Rotation of another string

Reverse a Linked List

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Input : ->30->25->20->15->10->5

Reversed : ->5->10->15->20->25->30

NOTE : Click Reverse a Linked List – Part 2 to see the another implementation of this problem.

Approach:

Read moreReverse a Linked List

Print All Elements of Two Dimensional Array in Spiral

Objective: This question was asked in Amazon interview for the Software development Engineer position, Write an algorithm to print all the elements of two dimensional array in spiral.
Example :

Print 2D array in Spiral
Print 2D array in Spiral

Input: Two dimensional array

Output: All array elements printed in spiral.

Approach:

Read morePrint All Elements of Two Dimensional Array in Spiral

Valid or Well Formed Parentheses | Part – 1

Objective: You have been asked to Write an algorithm to find Whether Given the Sequence of parentheses are well formed. This question was asked in the Amazon Interview.

Input: A String contains a sequence of parentheses

Output: true or false on whether parentheses are well formed or not

Approach:

  • Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
  • Read one character at a time and increment one of the counters
  • If any given point of time count of close parentheses is greater than the open one, return false
  • If at the end both counters are equal, return true

Example: { { } { } } – Well formed

{ { } { = Not well formed

Read moreValid or Well Formed Parentheses | Part – 1

Find an Element in 2 dimensional sorted array

Objective : Write an algorithm to find an Element in 2 dimensional array where rows and columns are sorted respectively.

Input: A two dimensional sorted array, arrA[][].

Sorted 2D array

 

Output : True or false based on whether element exists and its location

Approach:

Read moreFind an Element in 2 dimensional sorted array

Find Whether Given String is palindrome or Not.

Objective : Write an algorithm to find Whether Given String is palindrome or Not.

Input:  A String,

Output: true or false on whether string is palindrome or not

Approach:

  • Use recursive approach
  • Compare first and last characters if they are not same- return false
  • If they are same make, remove the first and last characters and make a recursive call. 

Example:

Jain niaJ => compare ‘J’ with ‘J’ =>returns true

ain nia => compare ‘a’ with ‘a’ =>returns true

in ni => compare ‘i’ with ‘i’ =>returns true

n n => compare ‘n’ with ‘n’ =>returns true

string length <2 => returns true

Read moreFind Whether Given String is palindrome or Not.

Find two Missing Numbers in a Sequence of Consecutive Numbers

Objective : Write an algorithm to find two Missing Numbers in a Sequence of Consecutive Numbers

Input:  Array, arrA[] with two missing numbers and Range

Output : Two missing numbers

Approach:

    • Approach is very simple, Add all the given numbers say S
    • Calculate sum of N numbers by formula n(n+1)/2 , say N
    • Find sum of two missing numbers a+b = N-S

Read moreFind two Missing Numbers in a Sequence of Consecutive Numbers

Find a Missing Number From a Sequence of Consecutive Numbers

Objective : You have been asked to Write an algorithm Find a Missing Number From a Sequence of Consecutive Numbers

Input:  Array, arrA[] with a missing number and Range

Output : missing number

Approach:

  • Approach is very simple, Add all the given numbers say S
  • Calculate sum of N numbers by formula n(n+1)/2 , say N
  • Find missing number m = N-S

Read moreFind a Missing Number From a Sequence of Consecutive Numbers