# Category: Microsoft Interview

## Construct a binary tree from given Inorder and Level Order Traversal

Objective: – Given a inorder and level order traversal, construct a binary tree from that. Input: Inorder and level order traversal Approach: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };...

## Print The Top View of a Binary Tree

Objective: – Given a binary tree, print it in Top View of it. What is Top View: Top view means when you look the tree from the top the nodes you will see will...

## Inorder Predecessor and Successor in Binary Search Tree

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...

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

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...

## Find Kth Smallest or Largest element in an Array.

Objective: Find Kth Smallest or Largest element in an Array Example: int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Output: The 4th smallest element is : 8 Approach:...

## Search an Element in a Rotated Sorted Array

Input: Rotated Sorted Array. What is Rotated Sorted Array. A sorted array is rotated around some pivot element. See the Example Below, array is rotated after 6. Approach:

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

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.

## Print All The Nodes Which are X distance from the Leaf Nodes

Objective: – Given Binary Tree, Print All The Nodes Which are X distance from the Leaf Nodes Example : Approach:

## Print All The Nodes Which are X distance from the Root

Objective: – Given Binary Tree, Print all the nodes which are X distance from the root Example : Appraoch:

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

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...

## Lowest Common Ancestor in a Binary Search Tree.

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...

## Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

Given a Sorted Array, Convert it into its Balanced Binary search TreeObjective: You have been given a sorted singly List, you need to convert it into balanced binary search tree. Why balanced binary tree...

## Given a binary tree, Find the Maximum Path Sum between Any Two Leaves

Objective: Given a binary tree, Find the maximum path sum from one leaf node to another. Input: A binary tree. Example: Approach:

## 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...

## 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....