[Binary Search Tree (BST)] Kth Smallest Element in a BST

230. Kth Smallest Element in a BST

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 
 * Runtime	: 59 ms
 * Memory	: 49.08 MB
 */
var kthSmallest = function(root, k) {
  const arr = dfsRecursiveInOrder(root);

  return arr[k - 1];
};

var dfsRecursiveInOrder = function (node, arr = []) {
  if(node) {
    if(node.left) 
      dfsRecursiveInOrder(node.left, arr);

    arr.push(node.val);

    if(node.right) 
      dfsRecursiveInOrder(node.right, arr);
        
  }
  return arr;
}

본 해답은 코드만으로도 의미를 파악할 수 있습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using inorder iterative

해답의 전문은 링크를 확인해주세요.

/**
 * Runtime	: 67 ms
 * Memory	: 48.04 MB
 */
var kthSmallest = function(root, k) {
  let n = 0
  let stack = []
  let current = root
  while (current || stack.length > 0) {
    while (current) {
        stack.push(current)
        current = current.left
    }
    current = stack.pop()
    n += 1
    if (n === k) return current.val
    current = current.right
  }
};

필자의 해답과 달리 반복을 사용하였습니다. 반복을 사용한 해답은 설명을 위해 루프 마다 stack의 상태값이 필요해보입니다. 따라서 재귀를 쓰는 방법이 더 직관적이라고 생각합니다.