Portfolio


Input: root = [3,1,4,null,2], k = 1
Output: 1


Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3


var kthSmallest = function(root, k) {
    const arr = [];
    
    const dfs = (node) => {
        arr.push(node.val);
        
        if(node.left){
            dfs(node.left);
        }
        
        if(node.right){
            dfs(node.right);
        }
    }
    
    if(!root){
        return;
    }
    
    dfs(root);
    
    arr.sort((a, b) => a - b);
    
    return arr[k - 1];
};


const check = (result, k) => {
  return result.length === k;
};

const treverseByInOrderUntilK = (node, k, result = []) => {
  if (check(result, k)) {
    return result;
  }

  if (!node.left && !node.right) {
    result.push(node.val);
    return result;
  }

  if (node.left) {
    result = treverseByInOrderUntilK(node.left, k, result);
  }

  if (!check(result, k)) {
    result.push(node.val);
  }

  if (node.right) {
    result = treverseByInOrderUntilK(node.right, k, result);
  }

  return result;
};

const kthSmallest = (root, k) => {
  return treverseByInOrderUntilK(root, k).pop();
};


var kthSmallest = function(root, k) {
    const arr = [];
    
    const dfs = (node) => {
        if(!node) return;
        
        arr.push(node.val);

        node.right && dfs(node.right);
        node.left && dfs(node.left);
    }
    
    dfs(root);
    arr.sort((a, b) => a - b);
    
    return arr[k -1];
};

Kth Smallest Element in a BST

풀이