Find the number of times a Sorted array is Rotated
Question: You are given an array that is rotated clockwise, you need to find the number of times the array is rotated. Example 1: array = {5, 6, 1, 2, 3, 4} Output = 2 Times. Why? Because, the sorted array will be {1, 2, 3, 4, 5, 6} on first rotation it will be […]
Find the first and last occurrence of an element
Question: Given an array sorted in ascending order with repeated elements and given the key. Find the first and last occurrence of that key. Example: array = {2, 3, 4, 4, 4, 5, 6, 7, 8}; key = 4. Here “4” is repeated 3 times. We need to send the starting and ending occurrence of […]
Order-Agnostic Binary Search
Question: Given an array whose order of sorting is unknown and a key. You need to check if the key is present or not using binary search. Solution: As the question stated, we dont know the order of the array. Our first step is to get to know the order of the array. How do […]
Binary search on an array that is in descending order
Question: Given an array in descending order and a key. You need to check if the key is present or not using binary search. Example: Array = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 Key = 2 Output: Key is found. Solution: Solution is very simple. First we calculate the mid index, […]
Get the count full nodes in a Binary
Problem statement: You are given root node of a tree and you need to find the number of full node in that tree. A node will be considered as full node if it has both left and right child. Consider the image below: Total number of full nodes are 3. This problem can by solved […]
Get count Non-Leaf nodes in a Binary Tree
Problem statement: You are given root node of a tree and you need to find the number of non leaf node in that tree. Consider the image below: Total number of non leaf node are 3. This problem can by solved by traversing the tree and keep the count of number of non leaf nodes. […]
Display all the leaf nodes from left to right and right to left in a tree
Consider the below image You need to print the leaf node: Form left to right: 7, 15, 18, 30 Form right to left : 30, 18, 15, 7 Solution in C++ #include <iostream> #include <queue> #include <stack> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; […]
Get depth of Odd level which contains Leaf node in Binary Tree
The solution is very simple. We need to traverse the tree from root node. We need to keep track of the current level of the node. Increment the current level once you go left or right subtree. Return max depth of an odd level. Solution in C++ #include <iostream> #include <queue> #include <stack> using namespace […]
Get deepest Left Leaf Node in Binary Tree
Question: Given a binary tree root node, get the deepest left leaf node Example: Consider the image given below and its mirror. From the above image, node 7 is the deepest left leaf node. Solution in C++ #include <iostream> #include <queue> #include <stack> using namespace std; // structure to hold binary tree node struct Node […]
Get Vertical Sum of Binary Tree
Problem Statement: You are given a root node, you need to calculate the vertical sum of the tree. Consider the image below Vertical-Line-1: has only one node 7 => vertical sum is 7 Vertical-Line-2: has only one node 10 => vertical sum is 10 Vertical-Line-3: has three nodes: 16, 15,18 => vertical sum is 16 […]