230. Kth Smallest Element in a BST
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Để tìm phần tử nhỏ thứ k trong một cây nhị phân tìm kiếm (BST), bạn nên tận dụng tính chất BST: Khi duyệt theo thứ tự inorder, các giá trị node sẽ dược duyệt theo thứ tự tăng dần. Do đó, chỉ cần duyệt inorder và đếm số node đã đi qua, khi đến node thứ k thì đó chính là đáp án
Có hai cách phổ biến:
Cả hai đều có độ phức tạp O(H + k), với H là chiều cao cây.
Time and space complexity
Approach - Recursive inorder traversal
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function kthSmallest(root: TreeNode | null, k: number): number {
16 let res = -1;
17 let count = k;
18 function dfs(node: TreeNode | null): void {
19 if (!node) return;
20 dfs(node.left);
21 count--
22 if (count === 0) {
23 res = node.val
24 return
25 }
26 dfs(node.right)
27 }
28 dfs(root)
29
30 return res;
31};