# 703. Kth Largest Element in a Stream

題目：<https://leetcode.com/problems/kth-largest-element-in-a-stream/>

解法：使用 binary search tree，並保持只有 k 個節點，第 k 大的值即為 BST的最小值。

Python3：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def treeToList(root):
    if not root:
        return []
    from collections import deque
    nodes = deque()
    nodes.append(root)
    arr = []
    arr.append(root.val)
    while len(nodes):
        node = nodes.popleft()
        if node.left:
            nodes.append(node.left)
            arr.append(node.left.val)
        else:
            arr.append(None)
        if node.right:
            nodes.append(node.right)
            arr.append(node.right.val)
        else:
            arr.append(None)
    return arr

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.size = 0
        self.root = None
        for num in nums:
            self.add(num)
    
    def add(self, val: int) -> int:
        if self.size < self.k:
            self.insertIntoBST(val)
            self.size += 1
        else:
            if val > self.minVal():
                self.insertIntoBST(val)
                self.deleteMinNode()
        return self.minVal()

    def insertIntoBST(self, val: int):
        if not self.root:
            self.root = TreeNode(val)
            return;
        parent = None
        cur = self.root
        while cur:
            parent = cur
            if val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        if val < parent.val:
            parent.left = TreeNode(val)
        else:
            parent.right = TreeNode(val)

    def minVal(self) -> int:
        cur = self.root
        while cur.left:
            cur = cur.left
        return cur.val
    
    def deleteMinNode(self):
        delParent = None
        delNode = self.root
        while delNode.left:
            delParent = delNode
            delNode = delNode.left
        if delParent is None:
            self.root = delNode.right
        else:
            delParent.left = delNode.right
        
if __name__ == '__main__':
    k = 1
    nums = []
    
    obj = KthLargest(k, nums)
    print(obj.add(-3))
    print(obj.add(-2))
    print(obj.add(-4))
    print(obj.add(0))
    print(obj.add(4))

C：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void printLevelOrderWithNull(struct TreeNode* root) {
    struct TreeNode * bfs[10000] = {};
    bfs[0] = root;
    int i = 0, len = 1;
    printf("%d ", root->val);
    while (i < len) {
        if (bfs[i]->left != NULL) {
            bfs[len++] = bfs[i]->left;
            printf("%d ", bfs[i]->left->val);
        } else
            printf("null ");
        if (bfs[i]->right != NULL) {
            bfs[len++] = bfs[i]->right;
            printf("%d ", bfs[i]->right->val);
        } else
            printf("null ");
        i++;
    }
    printf("\n");
}

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    if (root == NULL)
        return node;
    struct TreeNode *parent = NULL, *cur = root;
    while(cur != NULL) {
        parent = cur;
        if (val < cur->val)
            cur = cur->left;
        else
            cur = cur->right;
    }
    if (val < parent->val)
        parent->left = node;
    else
        parent->right = node;
    return root;
}

int minVal(struct TreeNode* root) {
    struct TreeNode* cur = root;
    while (cur->left != NULL)
        cur = cur->left;
    return cur->val;
}

struct TreeNode* deleteMinNode(struct TreeNode* root) {
    struct TreeNode *delParent = NULL, *delNode = root;
    while (delNode->left != NULL) {
        delParent = delNode;
        delNode = delNode->left;
    }
    if (delParent == NULL)
        return delNode->right;
    else
        delParent->left = delNode->right;
    return root;
}

typedef struct {
    int k;
    int size;
    struct TreeNode* root;
} KthLargest;

int kthLargestAdd(KthLargest* obj, int val) {
    if (obj->size < obj->k) {
        obj->root = insertIntoBST(obj->root, val);
        obj->size++;
    } else {
        if (val > minVal(obj->root)) {
            obj->root = insertIntoBST(obj->root, val);
            obj->root = deleteMinNode(obj->root);
        }
    }
    return minVal(obj->root);
}

KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
    KthLargest* obj = (KthLargest*)malloc(sizeof(KthLargest));
    obj->k = k;
    obj->size = 0;
    obj->root = NULL;
    for (int i = 0; i < numsSize; i++) {
        kthLargestAdd(obj, nums[i]);
    }
    return obj;
}

void TreeNodeFree(struct TreeNode* root) {
    if (root == NULL)
        return;
    TreeNodeFree(root->left);
    TreeNodeFree(root->right);
    free(root);
    return;
}

void kthLargestFree(KthLargest* obj) {
    TreeNodeFree(obj->root);
    free(obj);
    return;
}

int main()
{
    int k = 1;
    int nums[] = {};
    int numsSize = 0;
    
    KthLargest* obj = kthLargestCreate(k, nums, numsSize);
    printf("%d\n", kthLargestAdd(obj, -3));
    printf("%d\n", kthLargestAdd(obj, -2));
    printf("%d\n", kthLargestAdd(obj, -4));
    printf("%d\n", kthLargestAdd(obj, 0));
    printf("%d\n", kthLargestAdd(obj, 4));
    kthLargestFree(obj);
    return 0;
}

###### tags: `leetcode` `binary tree` `binary search tree`