Expert | Algorithms

Construct a Binary Tree from Given Inorder and Depth-First-Search.

August 31, 2019December 30, 2014 by Sumit Jain

Objective: – Given a 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 };

Inorder Predecessor and Successor in Binary Search Tree

August 31, 2019December 29, 2014 by Sumit Jain

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:

Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

August 31, 2019December 28, 2014 by Sumit Jain

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, ask to solve in O(1).

Better Solution : Time Complexity : O(n) Space Complexity: O(1)

Use Quick sort technique.

Take the pivot element as 0 and do the first round of Quick Sort.
After above step you will have all the negative elements on left and all the positive elements on the right.

Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

August 31, 2019December 28, 2014 by Sumit Jain

Objective: Given an array of size of N and number k. Find all elements in an Array which appears 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:

Print All The Nodes Which are X distance from the Given Node

August 31, 2019December 8, 2014 by Sumit Jain

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 the Distance between Two Nodes of a Binary Tree.

August 31, 2019December 8, 2014 by Sumit Jain

Objective: – Given nodes in a binary tree, find the distance between them.

Example :

Approach:

Construct a binary tree from given Inorder and Postorder Traversal

August 31, 2019December 8, 2014 by Sumit Jain

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

Appraoch:

int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };

int[] postOrder = { 4, 5, 2, 6, 7, 3, 1 };.

Lowest Common Ancestor in a Binary Tree (Not Binary Search Tree).

August 31, 2019November 18, 2014 by Sumit Jain

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:

Make a Binary Tree from Given Inorder and Preorder Traveral.

August 31, 2019November 18, 2014 by Sumit Jain

Objective: – Given a inorder and preorder traversal, construct a binary tree from that.

Input: Inorder and preorder traversals

Approach:

int [] inOrder = {2,5,6,10,12,14,15};

int [] preOrder = {10,5,2,6,14,12,15};

First element in preorder[] will be the root of the tree, here its 10.
Now the search element 10 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.

Print All The Permutations Of a String

August 31, 2019November 14, 2014 by Sumit Jain

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:

Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern

August 31, 2019November 10, 2014 by Sumit Jain

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.

Level Order Traversal in Zig Zag pattern OR Print in Spiral

Inorder Successor in Binary Search Tree without Using Parent link

August 31, 2019September 27, 2014 by Sumit Jain

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

Input: A binary search tree, a node x

Output: Inorder successor of node x.

Inorder Successor in Binary Search Tree Using Parent link

August 31, 2019September 27, 2014 by Sumit Jain

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

Input: A binary search tree with nodes liked to its parents, a node x

Output: The inorder successor of node x.

In a Binary Tree, Create Linked Lists of all the nodes at each depth.

August 31, 2019September 22, 2014 by Sumit Jain

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:

Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

August 14, 2020August 4, 2014 by Sumit Jain

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