# Binary Search Tree

###### tags: `LeetCode筆記`


It is noteworthy that **inorder traversal** in BST will be in **ascending order**.
Therefore, the inorder traversal is the most frequent used traversal method of a BST.

## :memo: 一、Basic Operation
### 1. Search
#### recursion1:

TreeNode* searchBST(TreeNode* root, int target) {
        if (!root || root->val == target) {
            return root;
        }
        if (target < root->val) {
            return searchBST(root->left, target);
        }
        return searchBST(root->right, target);
    }

#### recursion2:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) {
            return nullptr;
        }
        
        if (val < root->val) {
            return searchBST(root->left, val);
        }
        else if (val > root->val) {
            return searchBST(root->right, val);
        }
        else {
            return root;
        }
        
        return nullptr;
    }
};

#### iteration:

TreeNode searchBST(TreeNode root, int target) {
        TreeNode cur = root;
        while (cur != null && cur.val != target) {
            if (target < cur.val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return cur;
    }

### 2. Insertion
#### C

struct TreeNode* CreateTreeNode(int val)
{
    struct TreeNode* newnode = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    
    return newnode;
}

void insert(struct TreeNode* root, int val)
{
    
    if (val <= root->val)
    {
        if (root->left != NULL)
        {
            insert(root->left, val);
        }
        else
        {
            root->left = CreateTreeNode(val);
        }
    }
    else
    {
        if (root->right != NULL)
        {
            insert(root->right, val);
        }
        else
        {
            root->right = CreateTreeNode(val);
        }
    }
    
}

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) 
{
    if (root==NULL)
    {
        root = CreateTreeNode(val);
        
        return root;
    }
    
    insert(root,val);
    
    return root;
}

#### C++

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            TreeNode* newnode = new TreeNode(val);
            return newnode;
        }
        
        if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        }
        else if (val > root->val) {
            root->right = insertIntoBST(root->right, val);
        }
        
        return root;
    }
};

### 3. Deletion
#### C

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

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

struct TreeNode* deleteNode(struct TreeNode* root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }
    
    if (key > root->val)
    {
        root->right = deleteNode(root->right, key);
    }
    else if(key < root->val)
    {
        root->left = deleteNode(root->left, key);
    }
    else
    {
        if (root->left == NULL && root->right == NULL)
        {
            root = NULL;
        }
        else if (root->right != NULL)
        {
            root->val = successor(root);
            root->right = deleteNode(root->right, root->val);
        }
        else
        {
            root->val = predecessor(root);
            root->left = deleteNode(root->left, root->val);
        }
    }
    
    return root;
}

#### C++

class Solution {
private:
    TreeNode* findSuccessor(TreeNode* root) {
        TreeNode* cur = root->right;
        while (cur && cur->left) {
            cur = cur->left;
        }
        
        return cur;
    }
    
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return nullptr;
        }
        
        if (root->val == key) {
            if (!root->left) {
                return root->right;
            }
            
            if (!root->right) {
                return root->left;
            }
            
            TreeNode* p = findSuccessor(root);
            root->val = p->val;
            root->right = deleteNode(root->right, p->val);
            return root;
        }
        
        if (root->val < key) {
            root->right = deleteNode(root->right, key);
        }
        else {
            root->left = deleteNode(root->left, key);
        }
        
        return root;
    }
};

## :memo: *Validate Binary Search Tree (Medium)


### 作法 recursion
宣告一個private TreeNode* prev去紀錄上一個root，因此只要root->val<=prev->val，就是false

class Solution {
private:
    TreeNode* prev = nullptr;
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        
        if (!isValidBST(root->left)) {
            return false;    
        }
        
        if (prev != nullptr && root->val <= prev->val) {
            return false;
        }
        
        prev = root;
        
        return isValidBST(root->right);
    }
};

### 作法 iteration

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode* prev = nullptr;

        while (!stk.empty() or root != nullptr) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();

            if (prev != nullptr and root->val <= prev->val) {
                return false;
            }
            prev = root;
            root = root->right;
        }

        return true;
    }
};

## :memo: *Inorder Successor in BST (Medium)


### 作法1
利用flag去判斷找到p，然後往下traverse後的第一個就是successor，assign給q後，flag=0，並且return，但是會繼續traverse所以慢

### 作法2
利用BST的特性，比較p和root的值，然後用一個變數successor去紀錄(當p的值>root的值)會往左(先successor=root再root=root->left)

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* successor = nullptr;
        
        while (root != nullptr) {
            if (p->val >= root->val) {
                root = root->right;
            }
            else {
                successor = root;
                root = root->left;
            }
        }
        
        return successor;
    }
};

## :memo: Binary Search Tree Iterator (Medium)


### 作法 C
建一個global struct的變數list去存，然後traverse函數中的是雙指標obj去跑next，回傳值都是看list那一個

typedef struct {
    int val;
    struct BSTIterator* next;
}BSTIterator;

BSTIterator* list;

void traverse(BSTIterator** obj, struct TreeNode* root) {
    if (root == NULL)
    {
        return;
    }
    
    if (root->left)
    {
        traverse(obj, root->left);
    }

    BSTIterator* newnode = (BSTIterator*) malloc(sizeof(BSTIterator));
    newnode->val = root->val;
    newnode->next = NULL;
    
    (*obj)->next = newnode;
    (*obj) = (*obj)->next;
    
    // printf("%d\n", (*obj)->val);
    
    if (root->right)
    {
        traverse(obj, root->right);
    }
}

BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
    BSTIterator* head = (BSTIterator*) malloc(sizeof(BSTIterator));
    head->val = 0;
    head->next = NULL;
    
    BSTIterator* p;
    p = head;
    
    traverse(&head, root);
    
    list = p;
    
    return p;
}

int bSTIteratorNext(BSTIterator* obj) {  
    list = list->next;
    
    return list->val;
}

bool bSTIteratorHasNext(BSTIterator* obj) {
    if (list->next)
    {
        return true;
    }
    
    return false;
}

void bSTIteratorFree(BSTIterator* obj) {
    BSTIterator* p;
    
    while (obj != NULL)
    {
        p = obj;
        obj = obj->next;
        free(p);
    }
}

### 作法 C++
大while包住(用stack跑小while一直往左子樹後root=root->right)

class BSTIterator {
private:
    vector<int> list;
    int index = 0;
    
public:
    BSTIterator(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* prev = nullptr;
        
        while (!s.empty() or root != nullptr) {

            while (root != nullptr) {
                s.push(root);
                root = root->left;
            }
            
            root = s.top();
            s.pop();
            
            list.push_back(root->val);
                        
            root = root->right;
            
        }
        
    }
    
    int next() {
        if (index < list.size()) {
            return list[index++];    
        }
        
        return 0;
    }
    
    bool hasNext() {
        if (index >= list.size()) {
            return false;    
        }
        
        return true;
    }
};

## :memo: Kth Largest Element in a Stream (Easy)

### 作法

struct Node {
    Node* left;
    Node* right;
    int val;
    int cnt;
    Node(int v, int c) : left(NULL), right(NULL), val(v), cnt(c) {}
};

class KthLargest {
private:
    Node* insertNode(Node* root, int num) {
        if (!root) {
            return new Node(num, 1);	    // return a new node if root is null
        }
        if (root->val < num) {			// insert to the right subtree if val > root->val
            root->right = insertNode(root->right, num);
        } else {						// insert to the left subtree if val <= root->val
            root->left = insertNode(root->left, num);
        }
        root->cnt++;
        return root;
    }
    int searchKth(Node* root, int k) {
        // m = the size of right subtree
        int m = root->right ? (root->right)->cnt : 0;
        // root is the m+1 largest node in the BST
        if (k == m + 1) {
            return root->val;
        }
        if (k <= m) {
            // find kth largest in the right subtree
            return searchKth(root->right, k);
        } else {
            // find (k-m-1)th largest in the left subtree
            return searchKth(root->left, k - m - 1);
        }
    }
    Node* root;
    int m_k;
public:
    KthLargest(int k, vector<int> nums) {
        root = NULL;
        for (int i = 0; i < nums.size(); ++i) {
            root = insertNode(root, nums[i]);
        }
        m_k = k;
    }
    
    int add(int val) {
        root = insertNode(root, val);
        return searchKth(root, m_k);
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

## :memo: *Lowest Common Ancestor of a Binary Search Tree (Medium)


### 作法
這題因為是BST，所以可以利用val去找共同祖先，不過一般的Binary Tree就不行了

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (p->val > root->val && q->val > root->val)
    {
        return lowestCommonAncestor(root->right, p, q);
    }
    else if (p->val < root->val && q->val < root->val)
    {
        return lowestCommonAncestor(root->left, p, q);
    }
    else
    {
        return root;
    }
}

## :memo: Contains Duplicate III (Hard)
Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

### 作法
很簡單的想法寫成程式碼就好，要注意的是要改成long long t，先排序後再暴力解

void swap(int *p, int *q)
{
    int t = *p; 
    *p = *q;
    *q = t;
}

void sort(int* nums, int* indexes, int low, int high)
{
    int l = low, h = high;
    int v = nums[l + (h - l) / 2];
    while (l <= h)
    {
        while(nums[l] < v) l++;
        while(nums[h] > v) h--;
        if (l <= h)
        {
            swap(nums + l, nums + h);
            swap(indexes + l, indexes + h);
            l++, h--;
        }
    }
    if(h > low)
        sort(nums, indexes, low, h);
    if(l < high)
        sort(nums, indexes, l, high);
}

bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int k, long long t) {
    int* indexes = (int*) malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++)
    {
        indexes[i] = i;
    }
    
    sort(nums, indexes, 0, numsSize - 1);
    
    for (int i = 0; i < numsSize; i++)
    {
        long long top = nums[i] + t;
        for (int j = i + 1; j < numsSize && nums[j] <= top; j++)
        {
            if (abs(indexes[i] - indexes[j]) <= k)
            {
                return true;
            }
        }
    }
    
    return false;
}

### 作法 Bucket

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, long t) {
        if (nums.size() < 2 || t < 0 || k < 0) return false;
        int minx = INT_MAX, maxx = INT_MIN;
        //find the minimum and maximum to determine the number of buckets
        for (auto & i : nums) {
            minx = min(minx, i);
            maxx = max(maxx, i);
        }
        int n = ((long)maxx - (long)minx) / (t + 1) + 1;
        //initialize by -(k + 1)
        vector<int> buckets(n, -(k + 1));
        for (int i = 0, j; i < nums.size(); i++) {
            //get the index of bucket
            j = ((long)nums[i] - (long)minx) / (t + 1);
            //check the two constraints
            if ((i - buckets[j] <= k) || (j && i - buckets[j - 1] <= k && (long)nums[i] - (long)nums[buckets[j - 1]] <= t) || (j < n - 1 && i - buckets[j + 1] <= k && (long)nums[buckets[j + 1]] - (long)nums[i] <= t))
                return true;
            buckets[j] = i;
        }
        return false;
    }
};

### 作法 Binary Search Tree

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        if (nums.size() == 0) {
            return false;
        }
        
        if (indexDiff == 0) {
            return false;
        }
        
        multiset<int> bst;
        
        for (int i = 0; i < nums.size(); i++) {
            const auto it = bst.lower_bound(nums[i] - valueDiff);
            if (it != bst.end() and abs(*it - nums[i]) <= valueDiff) {
                return true;
            }
            
            bst.insert(nums[i]);
            
            if (bst.size() > indexDiff) {
                bst.erase(bst.find(nums[i - indexDiff]));
            }
        }
        
        return false;
    }
};

## :memo: 二、Height-Balanced BST
參考網址:
https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/143/appendix-height-balanced-bst/1021/

## :memo: *Balanced Binary Tree (Easy)
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

### 作法
計算左子樹與右子樹高度差是否<2，然後往左往右遞迴，並且去&&3個結果

int height(struct TreeNode* root) {
    if (root == NULL)
    {
        return -1;
    }
    
    return 1 + fmax(height(root->left), height(root->right));
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    
    return abs(height(root->left) - height(root->right)) < 2 && isBalanced(root->left)  && isBalanced(root->right);
}

### 作法 最快code

class Solution {
public:
    pair<bool,int> isBlanced(TreeNode* root) {
        if(root==NULL) {
            pair<bool,int>p = make_pair(true,0);
            return p;
        }

        pair<bool,int>left = isBlanced(root->left);
        pair<bool,int>right = isBlanced(root->right);


        bool leftans = left.first;
        bool rightans = right.first;
        bool diff = abs(left.second - right.second) <= 1;

        pair<bool,int>ans;
        ans.second = max(left.second, right.second) + 1;

        if (leftans && rightans && diff ) {
            ans.first = true;
        }
        else {
            ans.first = false;
        }
        return ans;
    }

    bool isBalanced(TreeNode* root) {
        return isBlanced(root).first;
    }
};

## :memo: Convert Sorted Array to Binary Search Tree (Easy)
把排序過的陣列轉成BST

### 作法 C
陣列分成左半右半去建root，一直向左向右遞迴

struct TreeNode* createTreeNode(int val)
{
    struct TreeNode* newnode = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    
    return newnode;    
}

struct TreeNode* helper(int* nums, int left, int right)
{
    if (left > right)
    {
        return NULL; 
    }
    
    int p = (left + right) / 2;
    
    struct TreeNode* root = createTreeNode(nums[p]);
    root->left = helper(nums, left, p - 1);
    root->right = helper(nums, p + 1, right);
    
    return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize)
{
    return helper(nums, 0, numsSize - 1);
}

### 做法 C++

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) {
            return nullptr;
        }
        if (nums.size() == 1) {
            return new TreeNode(nums[0]);
        }
        
        int middle = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[middle]);
        
        vector<int> leftInts(nums.begin(), nums.begin() + middle);
        vector<int> rightInts(nums.begin() + middle + 1, nums.end());
        
        root->left = sortedArrayToBST(leftInts);
        root->right = sortedArrayToBST(rightInts);
        
        return root;
    }
};

## :memo: 刷題檢討
二元搜尋樹的問題偏簡單，要利用到數值與數值之間的關係，基本的搜尋新增很容易，**刪除有點複雜，要去多弄熟，可以和二元樹一起複習**