Objective: – Given a preorder traversal, construct BST from that. Input: Preorder traversal Similar Problem: This problem is similar to … Read more
Objective: – Given an inorder and preorder traversal, construct a binary tree from that.
Input: Inorder traversal and Depth-First-Search.
Approach:
int[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 };
int[] DFS = { 1, 2, 4, 8, 5, 3, 6, 7, 9 };
Objective: – Given a Binary Search Tree, Find predecessor and Successor of a given node.
What is Predecessor and Successor :
When you do the inorder traversal of a binary tree, the neighbors of given node are called Predecessor(the node lies behind of given node) and Successor (the node lies ahead of given node).
Example:
Approach:
Objective: Given an array arrA[] which has negative and positive elements, rearrange the array in such a manner that positive and negative elements occupy the alternate positions and if there are extra positive or negative elements are left then append it to the end.
Examples:
int[] arrA = { 1, 2, -3, -4, -5, 6, -7, -8, 9, 10, -11, -12, -13, 14 };
Output: -13 9 -3 10 -5 6 -7 2 -12 1 -11 14 -4 -8
Naive Solution: Take the extra space of O(n), do the linear scan twice, and fill the positive and negative elements at alternate positions.
But the problem becomes interesting when you have asked not to use any extra space, and ask to solve in O(1).
Better Solution : Time Complexity : O(n) Space Complexity: O(1)
Use Quick sort technique.
Objective: Given an array of size of N and number k. Find all elements in an Array which appear more than N/K times.
Input: Array [] and number k.
Example:
int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 };
K = 4
N/k = 14/4 = 3
Output will be [3,4] they appear 5, 4 times respectively.
Approach:
Objective: – Given Binary Tree, Print All The Nodes Which are X distance from the Given Node.
Example :
Approach:
Quite Tricky solution, i will explain using the example given in the picture.
Find out all the nodes which are at distance ‘3’ from the given node 5.
Objective: – Given nodes in a binary tree, find the distance between them.
Example :
Approach:
Objective: – Given a inorder and postorder traversal, write an algorithm to construct a binary tree from that. This problem was asked in the Microsoft coding competition.
Input: Inorder and postorder traversals
Similar Problems: Make a Binary Tree from Given Inorder and Preorder Traveral.
Appraoch:
int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };
int[] postOrder = { 4, 5, 2, 6, 7, 3, 1 };.
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: – 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 String, print all the permutations of it.
Input: A String
Output: Print all the permutations of a string
Example:
Input : abc
Output:
abc acb bac bca cba cab
Approach:
Objective: Given a binary Tree, Do Level Order Traversal in Zig Zag pattern OR Print in Spiral
Input: A Binary Tree
Output: Order Traversal in Zig Zag pattern OR Print in Spiral.
Better Solution :
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:
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: