Scribd
Upload
40 views4 pages

Priority Queues: 1. Find K Numbers With Most Occurrences in The Given Array

The document discusses two data structures - priority queues and binary trees. It provides examples and problems related to each: 1) For priority queues, it gives an example of finding the top k most frequent numbers in an array. 2) For binary search trees (BSTs), it lists problems about merging two BSTs, transforming a BST into a "greater sum tree", and checking if two BSTs are identical without reconstructing the trees. 3) For binary trees, it discusses printing the left view of a binary tree and swapping node values based on their position in the tree.

Uploaded by

Shailesh Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
40 views4 pages

Priority Queues: 1. Find K Numbers With Most Occurrences in The Given Array

The document discusses two data structures - priority queues and binary trees. It provides examples and problems related to each: 1) For priority queues, it gives an example of finding the top k most frequent numbers in an array. 2) For binary search trees (BSTs), it lists problems about merging two BSTs, transforming a BST into a "greater sum tree", and checking if two BSTs are identical without reconstructing the trees. 3) For binary trees, it discusses printing the left view of a binary tree and swapping node values based on their position in the tree.

Uploaded by

Shailesh Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Priority Queues

1. Find k numbers with most occurrences in the given array

Given an array of n numbers and a positive integer k. The problem is to find k


numbers with most occurrences, i.e., the top k numbers having the maximum
frequency. If two numbers have same frequency then the larger number should be
given preference. The numbers should be displayed in decreasing order of their
frequencies. It is assumed that the array consists of k numbers with most
occurrences.

Example:

Input : arr[] = {3, 1, 4, 4, 5, 2, 6, 1},


k=2
Output : 4 1
Frequency of 4 = 2
Frequency of 1 = 2
These two have the maximum frequency and
4 is larger than 1.

BST

1. Merge two BSTs

Given two BSTs, merge them and return the pointer to the new head of the BST. Try
to do them with limited space and time complexities.
2. BST Sum tree

Given a BST, transform it into greater sum tree where each node contains sum of all
nodes greater than that node.

3. Check for Identical BSTs without building the trees

Given two arrays which represent a sequence of keys. Imagine we make a Binary
Search Tree (BST) from each array. We need to tell whether two BSTs will be
identical or not without actually constructing the tree.

Let the input arrays be a[] and b[]

a[] = {2, 4, 1, 3} will construct following tree.

2
/ \
1 4
/
3

b[] = {2, 4, 3, 1} will also also construct the same tree.

2
/ \
1 4
/
3

So the output is "True"


Binary Tree

1. Print Left View of a Binary Tree

Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes
visible when tree is visited from left side. Left view of following tree is 12, 10, 25.

12
/ \
10 30
/ \
25 40

2. Swap left right sum

Given a BST replace left node data with the sum of the nodes in the right of its
parent, and right node data with sum of the nodes in the left of the parent.

Note: Do not create another tree, do it in-place

Example:

6
/ \
4 8
/ \ /\
3 5 7 9
6
/ \
24 12
/ \ / \
5 3 9 7

You might also like