Leetcode #230 Kth Smallest Element in a BST

[yokostan]

Binary Search:

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int count = countNodes(root.left);
        if (count == k - 1) return root.val;
        else if (count < k - 1) return kthSmallest(root.right, k - count - 1);
        return kthSmallest(root.left, k);
    }

    private int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

DFS In-order recursive:

class Solution {
    private static int number = 0;
    private static int count = 0;

  public int kthSmallest(TreeNode root, int k) {
      count = k;
      helper(root);
      return number;
  }

  public void helper(TreeNode n) {
      if (n.left != null) helper(n.left);
      count--;
      if (count == 0) {
          number = n.val;
          return ;
      }
      if (n.right != null) helper(n.right);
  }
}

DFS in-order iterative:

class Solution {
  public int kthSmallest(TreeNode root, int k) {
      Stack<TreeNode> stack = new Stack<>();

      while (root != null) {
          stack.push(root);
          root = root.left;
      }

      while (k != 0) {
          TreeNode n = stack.pop();
          k--;
          if (k == 0) return n.val;
          TreeNode right = n.right;
          while (right != null) {
              stack.push(right);
              right = right.left;
          }
      }

      return -1;
  }
}