Post

Kth Smallest Element in a BST

Posted
By Seonghun Jung 1 min read

1. Problem Statement

2. Algorithm Design and Approach

3. Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution
{
public:
    int kthSmallest(TreeNode *root, int k)
    {
        vector<TreeNode *> stack;
        TreeNode *node = root;

        while (true)
        {

            while (node != nullptr)
            {
                stack.push_back(node);
                node = node->left;
            }
            node = stack.back();
            stack.pop_back();
            
            if (--k == 0)
                return node->val;
            node = node->right;
        }
    }
};

4. Example Walkthrough

5. Conclusion

  • stack으로 제일 왼쪽에 있는 아이템 관리
Algorithm, Sliding Window
c++ leet code
This post is licensed under CC BY 4.0 by the author.