Kth Smallest Element in a BST

Solution

Using DFS

/**
 * 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:
    int smallestK;
    int count = 0;
    int k = 0;
    int kthSmallest(TreeNode* root, int k) {
        this->k = k;
        dfs(root);
        return smallestK;
        
    }
    void dfs(TreeNode* root) {
        if(root == NULL) return;
        dfs(root->left);
        count++;
        
        if(count == k) {
            smallestK = root->val;
            return;
        }
        dfs(root->right);
    }
};

Updating Size at the time of Building Tree

class Node {
    public:
    int val;
    int size;
    Node *left;
    Node *right;
    Node(int v) {
        val = v;
        size = 1;
        left = nullptr;
        right = nullptr;
    }
};

class BinarySearchTree {
    public:
    Node* root = nullptr;
    int size = 0;

    BinarySearchTree() {}

    void addNum(int val) {
        root = addNode(root, val);
        size++;
        // printf("Added: %d\n", root->size);
    }

    int findKthNum(int k) {
        Node* n = findKthNode(root, k);
        if (n != nullptr) {
            return n->val;
        }
        return -1;
    }

    void printTree(Node* root, int indent) {
        if (root == nullptr) {
            return;
        }
        for (int i = 0; i < indent; i++) {
            printf("  ");
        }
        cout << root;
        printf(" %d (Size: %d)\n", root->val, root->size);
        // cout << root << " " << "Size"
        printTree(root->left, indent+1);
        printTree(root->right, indent+1);
    }

    Node* addNode(Node* root, int val) {
        if (root == nullptr) {
            return new Node(val);
        }
        root->size++;
        // printf("Inserting %d\t", val);
        // printf("at node: %d Size: %d\n", root->val, root->size);
        if (root->val >= val) {
            root->left = addNode(root->left, val);
            return root;
        }
        root->right = addNode(root->right, val);
        return root;
    }

    Node* findKthNode(Node* root, int k) {
        if (root == nullptr) { // assume that we never reach here
            return nullptr;
        }

        // printf("Finding %d at ", k);
        // cout << root << "\n";
        int leftSize = 0;
        if (root->left != nullptr) {
            leftSize = root->left->size;
        }
        if (k <= leftSize) {
            return findKthNode(root->left, k);
        } else if (k == leftSize + 1) {
            return root;
        } else {
            return findKthNode(root->right, k - 1 - leftSize);
        }
    }
};
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
*/

Also check: Find Median from Data Stream