nikoo28

A tree is called a binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right sub-trees of the root. Generic Binary Tree Types of Binary Trees Strict Binary Tree: A tree is called a strict binary tree if each node has exactly two children or no children. Full Binary Tree: A binary tree is called a full binary …

A tree is a data structure similar to a linked list but instead of each node simply pointing to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non-linear data structure. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. In trees ADT (Abstract Data Type), order of the elements is not important. If we need ordering information, linear data structures like linked lists, stacks, queues etc can be …

Question: Given an array arr[], that contains only 0’s and 1’s. Write a function that separate 0’s and 1’s in the array. Input: 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 Output: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 The objective of the problem is to segregate the array in two parts, and it is more popularly known as a variation of Dutch National Flag Problem. Method 1: The most naive method is to count …

Question: Given an array arr[], write a function that separates even and odd numbers. The function should print first all the even numbers and then the odd numbers. Input: 4, 8, 15, 16, 23, 42 Output: 4, 8, 16, 42, 23, 15 The objective of this problem is mainly to segregate the array in two halves. One half contains all the even numbers and one half contains all the negative numbers. Naive Method:- The most naive method is to allocate a separate empty array and then we fill it as …

In C, struct keyword must be used for declaring structure variables, but it is optional in C++. For example, following program gives error in C and works in C++. And following program works in both C and C++.

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 We discussed the basic 2 methods to approach this problem here:- Find majority element. (Method 1) Find majority element. (Method 2 , using sorting) It is recommended to have a look …

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 We discussed the most naive method to achieve this in our previous post. To improve the time complexity of our problem we can apply sorting technique. If we sort the array, …

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 The most basic method of solving this problem is to take two loops and maintain a count of each of the element. If the count reaches more than (n/2) for any …

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 We discussed the basic method to find the number of occurrences in this post. But here, in both the cases, the time complexity is not good. We can use some of the tricks studied earlier to find a time efficient method. What we can do is:- Find the first occurrence of the element. Find …

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 The most basic methodology to solve this problem is linear search. Just scan the array and count the number of occurrences. But this takes time O(n). We can improve the time complexity by using binary search. The steps involved in this method are:- Do a binary search and search for the data in the …