ES6 solutions; using successors (beats 91%) and iteration


  • 0
    Y

    Iterative

    function kthSmallest(treeNode, k) {
      if (treeNode === null) {
        return null
      }
      let i = 0
      const stack = []
      let node = treeNode
      while (node !== null || stack.length) {
        if (node) {
          stack.push(node)
          node = node.left
        } else {
          node = stack.pop()
          i++
          if (i === k) {
            return node.val
          }
          node = node.right
        }
      }
      return null
    }
    

    With an inefficient (always walks from the root) successor function

    function successor(treeNode, query) {
      if (!treeNode) {
        return null
      }
      const {left, right, val} = treeNode
      if (query >= val) {
        return successor(right, query)
      }
      // we can potentially find a "closer" successor by recursing left
      const leftSuccessor = successor(left, query)
      return leftSuccessor || treeNode
    }
    
    function getMin(treeNode) {
      let min = treeNode
      while (min && min.left) {
        min = min.left
      }
      return min
    }
    
    // https://leetcode.com/problems/kth-smallest-element-in-a-bst/
    function kthSmallest(treeNode, k) {
      let ithSmallest = getMin(treeNode)
      for (let i = 1; i < k; i++) {
        ithSmallest = successor(treeNode, ithSmallest.val)
      }
      return ithSmallest.val
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.