Open seungriyou opened 6 months ago
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
BST는 inorder traversal 하면 sorted 결과를 얻을 수 있다.
tree의 traversal은 recursion을 이용하면 쉽게 구현할 수 있다.
또한, 일반 함수가 아닌 generator 함수로도 구현할 수 있다.
O(n)
O(h)
Approach
BST는 inorder traversal 하면 sorted 결과를 얻을 수 있다.
tree의 traversal은 recursion을 이용하면 쉽게 구현할 수 있다.
또한, 일반 함수가 아닌 generator 함수로도 구현할 수 있다.
Complexity
O(n)(모든 노드 방문)O(h)(recursion stack = height)