# Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note: Recursive solution is trivial, could you do it iteratively?

# Related Problems

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

• MyCircularQueue(k): Constructor, set the size of the queue to be k.
• Front: Get the front item from the queue. If the queue is empty, return -1.
• Rear: Get the last item from the queue. If the queue is empty, return -1.
• enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
• deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
• isEmpty(): Checks whether the circular queue is empty or not.
• isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4


Note:

• All values will be in the range of [0, 1000].
• The number of operations will be in the range of [1, 1000].
• Please do not use the built-in Queue library.

## Solution: Simulate with an array

We need a fixed length array, and the head location as well as the size of the current queue.

We can use q[head] to access the front, and q[(head + size – 1) % k] to access the rear.

Time complexity: O(1) for all the operations.
Space complexity: O(k)

# Problem

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

You can return this binary search tree:

This tree is also valid:

# Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

# Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);


Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

# Solution: BST / Min Heap

Time complexity: O(nlogk)

Space complexity: O(k)

C++ / BST

C++ / Min Heap

# Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
4
/ \
2   7
/ \
1   3

And the value to search: 2


You should return this subtree:

      2
/ \
1   3


In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

# Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

Mission News Theme by Compete Themes.