Objective: – Find the Lowest Common Ancestor of two given nodes in a Binary Tree
What is Lowest Common Ancestor
In a given binary tree, The lowest common ancestor of two nodes n1 and n2 will be a node X such that node X will be the lowest node who has n1 and n2 as its descendants.
Similar Problem: Lowest Common Ancestor in a Binary Search Tree.
Example:
Input: A binary Tree and two nodes n1 and n2.
Appraoch:
Objective: – Find the Lowest Common Ancestor of two given nodes in a Binary Search Tree
What is Lowest Common Ancestor
In a given binary tree, The lowest common ancestor of two nodes n1 and n2 will be a node X such that node X will be the lowest node who has n1 and n2 as its descendants.
Similar Problem: Lowest Common Ancestor in a Binary Tree ( Not Binary Search Tree).
Example:
Input: A binary Search Tree and two nodes n1 and n2.
Appraoch:
Objective: – Given a inorder and preorder traversal, construct a binary tree from that.
Input: Inorder and preorder traversals
Similar Problem: Construct a binary tree from given Inorder and Postorder Traversal
Approach:
int [] inOrder = {2,5,6,10,12,14,15};
int [] preOrder = {10,5,2,6,14,12,15};
Objective: Given a sorted doubly linked list, convert it into Balanced binary search tree
Input: A Doubly Linked List
Example:
Approach:
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:
Objective: Given 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 Tree
Input: A binary search tree, a node x
Output: Inorder successor of node x.
Example:
Algorithms – Inorder Successor in Binary Search Tree Using Parent link
Objective: Given a Binary Search tree in which every node has a link to its parent, 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 without parent link
Inorder Successor in Binary Tree
Input: A binary search tree with nodes liked to its parents, a node x
Output: The inorder successor of node x.
Example:
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:
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.
Objective: Given a Binary tree create Linked Lists of all the nodes at each depth , say if the tree has height k then create k linked lists.
NOTE : This problem is very similar “Print binary tree, each level in one line“
Input: A binary tree
Output: K linked lists if the height of tree is k. Each linked list will have all the nodes of each level.
Example:
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:
Objective: Rearrange Positive and Negative Numbers of an Array so that one side you have positive numbers and other side with negative Integers without changing their respective order.
Example
: Input : 1 -2 3 -4 5 -6 7 -8 9 -10 ReArranged Output : -2 -4 -6 -8 -10 1 3 5 7 9
Input: An array with positive and negative numbers
Output: Modified array with positive numbers and negative numbers are on each side of the array.
Approach:
Method 1. One naive approach is to have another array of same size and navigate the input array and one scan place all the negative numbers to the new array and in second scan place all the positive numbers to new array. Here the Space complexity will be O(n). We have a better solution which can solve this in O(1) space.
Method 2: Divide and Conquer
Objective: Write an algorithm to find The Longest Sequence Of Prefix Shared By All The Words In A String. This interesting problem was asked in the Google interview for software engineer. This problem is bit tricky, it looks difficult but actually it is simple problem.
Input: A String
Output: The longest sequence of prefix common in all the words in a string
Example:
“Bedroom BedClock BedTable BedWall” => “Bed”
Approach: