Leetcode Study Day 41

Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:


Input: root = [4,2,6,1,3]
Output: 1
Example 2:


Input: root = [1,0,48,null,null,12,49]
Output: 1

My solution

My solution is to use breadth first search to store all the values of the nodes in the tree into a vector. Then we sort the vector. Then we use a for loop to find the minimum difference between the adjacent values in the vector. Then we return the minimum difference.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector <int> numbers;
    int getMinimumDifference(TreeNode* root) {
        queue<TreeNode* > treeQ;
        treeQ.push(root);
        while(!treeQ.empty()){
            TreeNode* node = treeQ.front();
            treeQ.pop();
            numbers.push_back(node->val);
            if(node->left) treeQ.push(node->left);
            if(node->right) treeQ.push(node->right);
        }
        sort(numbers.begin(), numbers.end());
        int n = numbers.size();
        if(n == 1) return numbers[0];
        int minDif = INT_MAX;
        for(int i = 1; i < n; i++){
            minDif = min(numbers[i]-numbers[i-1], minDif);
        }
        return minDif;
    }
};

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Example 1:


Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2:


Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
 

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104

My solution

(正所谓一招鲜吃遍天) As the saying goes, “one trick pays off”, I used the same method as the previous question. I used breadth first search to store all the values of the nodes in the tree into a vector. Then we sort the vector. Then we return the kth element in the vector.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector <int> numbers;
    int kthSmallest(TreeNode* root, int k) {
        queue<TreeNode* > treeQ;
        treeQ.push(root);
        while(!treeQ.empty()){
            TreeNode* node = treeQ.front();
            treeQ.pop();
            numbers.push_back(node->val);
            if(node->left) treeQ.push(node->left);
            if(node->right) treeQ.push(node->right);
        }
        sort(numbers.begin(),numbers.end());
        return numbers[k-1];
    }
};

Improved method

Since my code use a queue ana a vector, which is memory consuming, I found a better solution.

The property of a Binary Search Tree (BST) that makes in-order traversal effective for this task is that in-order traversal of a BST yields the nodes in ascending order. This means that as I traverse the tree in in-order fashion, the first node I encounter is the smallest, the second node is the second smallest, and so on.

So remember, when meeting a binary search tree problem, we always first consider inorder traversal.

class Solution {
public:
    int count = 0; // Counter for the number of processed nodes
    int result = -1; // Variable to store the kth smallest value

    void inOrder(TreeNode* node, int k) {
        if (node == nullptr || count >= k) return;
        
        inOrder(node->left, k); // Traverse the left subtree
        
        // Increment count and check if we've reached the kth smallest
        if (++count == k) {
            result = node->val; // Found kth smallest
            return;
        }
        
        inOrder(node->right, k); // Traverse the right subtree
    }

    int kthSmallest(TreeNode* root, int k) {
        inOrder(root, k);
        return result;
    }
};