230. Kth smallest element

230_solution1.c

#include "tree_node.h"

static void dfs(struct TreeNode *root, int *idx, int *res) {
  if (!root || *idx == 0)
    return;

  dfs(root->left, idx, res);
  if (*idx == 0)
    return; // answer found in the left subtree
  (*idx)--;

  if (*idx == 0) {
    *res = root->val;
    return;
  }

  dfs(root->right, idx, res);
}

int kthSmallest(struct TreeNode *root, int k) {
  int res = 0;
  dfs(root, &k, &res);
  return res;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

230_solution1.cpp

#include "tree_node.h"

class Solution {
public:
  int kthSmallest(TreeNode *root, int k) {
    int res;
    dfs(root, k, res);
    return res;
  }

  void dfs(TreeNode *root, int &idx, int &res) {
    if (!root || idx == 0) {
      return;
    }

    dfs(root->left, idx, res);
    if (idx == 0)
      return; // answer found in the left subtree
    idx--;

    if (idx == 0) {
      res = root->val;
      return;
    }

    dfs(root->right, idx, res);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

230_solution1.go

package trees

func kthSmallest(root *TreeNode, k int) int {
    res := 0

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil || k == 0 {
            return
        }

        dfs(node.Left)
        if k == 0 {
            return // answer found in the left subtree
        }
        k--

        if k == 0 {
            res = node.Val
            return
        }

        dfs(node.Right)
    }

    dfs(root)
    return res
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

230_solution1.java

class Solution {
    private int idx;
    private int res;

    public int kthSmallest(TreeNode root, int k) {
        idx = k;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode node) {
        if (node == null || idx == 0)
            return;

        dfs(node.left);
        if (idx == 0)
            return; // answer found in the left subtree
        idx--;

        if (idx == 0) {
            res = node.val;
            return;
        }

        dfs(node.right);
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

230_solution1.js

const TreeNode = require("./tree_node");

var kthSmallest = function (root, k) {
  let res = 0;

  const dfs = (node) => {
    if (!node || k === 0) return;

    dfs(node.left);
    if (k === 0) return; // answer found in the left subtree
    k--;

    if (k === 0) {
      res = node.val;
      return;
    }

    dfs(node.right);
  };

  dfs(root);
  return res;
};

tree_node.js

// 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;
}

module.exports = TreeNode;

230_solution1.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        idx, res = k, 0

        def dfs(node: Optional[TreeNode]) -> None:
            nonlocal idx, res
            if not node or idx == 0:
                return

            dfs(node.left)
            if idx == 0:
                return  # answer found in the left subtree
            idx -= 1

            if idx == 0:
                res = node.val
                return

            dfs(node.right)

        dfs(root)
        return res

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

230_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn kth_smallest(root: Link, k: i32) -> i32 {
        let (mut idx, mut res) = (k, 0);
        Self::dfs(&root, &mut idx, &mut res);
        res
    }

    fn dfs(node: &Link, idx: &mut i32, res: &mut i32) {
        let Some(n) = node else { return };
        if *idx == 0 {
            return;
        }
        let n = n.borrow();

        Self::dfs(&n.left, idx, res);
        if *idx == 0 {
            return; // answer found in the left subtree
        }
        *idx -= 1;

        if *idx == 0 {
            *res = n.val;
            return;
        }

        Self::dfs(&n.right, idx, res);
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}