Kth Smallest Element In A Bst

                                            
/**
 * 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) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* current = root;
        int count = 0;
        
        while (current != nullptr || !st.empty()) {
            while (current != nullptr) {
                st.push(current);
                current = current->left;
            }
            current = st.top();
            st.pop();
            count++;
            if (count == k) {
                return current->val;
            }
            current = current->right;
        }
        
        return -1; // Just to handle the case when k is out of range
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        int count = 0;
        int result = 0;
        
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            count++;
            if (count == k) {
                result = current.val;
                break;
            }
            current = current.right;
        }
        
        return result;
    }
}

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

class Solution(object):
    def kthSmallest(self, root, k):
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

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

void inorder(struct TreeNode* root, int k, int* count, int* result) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, k, count, result);
    (*count)++;
    if (*count == k) {
        *result = root->val;
        return;
    }
    inorder(root->right, k, count, result);
}

int kthSmallest(struct TreeNode* root, int k) {
    int count = 0;
    int result = 0;
    inorder(root, k, &count, &result);
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (true) {
            while (root != null) {
                stack.Push(root);
                root = root.left;
            }
            root = stack.Pop();
            if (--k == 0) {
                return root.val;
            }
            root = root.right;
        }
    }
}

                                            
/**
 * 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}
 */
var kthSmallest = function(root, k) {
    let sortedValues = [];
    
    const inorderTraversal = (node) => {
        if (node === null) {
            return;
        }
        
        inorderTraversal(node.left);
        sortedValues.push(node.val);
        inorderTraversal(node.right);
    }
    
    inorderTraversal(root);
    
    return sortedValues[k - 1];
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?, right?) {
 *         this.val = (val === undefined ? 0 : val)
 *         this.left = (left === undefined ? null : left)
 *         this.right = (right === undefined ? null : right)
 *     }
 * }
 */

function kthSmallest(root: TreeNode | null, k: number): number {
    const stack: TreeNode[] = [];
    let current: TreeNode | null = root;
    let count = 0;
    
    while (current || stack.length > 0) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        count++;
        if (count === k) {
            return current.val;
        }
        
        current = current.right;
    }
    
    return -1;
}

                                            
class Solution {

    /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     public $val = null;
     *     public $left = null;
     *     public $right = null;
     *     function __construct($value) {
     *         $this->val = $value;
     *     }
     * }
     */

    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Integer
     */
    function kthSmallest($root, $k) {
        $stack = [];
        while (true) {
            while ($root != null) {
                $stack[] = $root;
                $root = $root->left;
            }
            $root = array_pop($stack);
            $k--;
            if ($k == 0) {
                return $root->val;
            }
            $root = $root->right;
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var result = 0
        var count = 0
        
        func inorderTraversal(_ node: TreeNode?) {
            guard let node = node else { return }
            inorderTraversal(node.left)
            count += 1
            if count == k {
                result = node.val
                return
            }
            inorderTraversal(node.right)
        }
        
        inorderTraversal(root)
        return result
    }
}

                                            
class Solution {
    fun kthSmallest(root: TreeNode?, k: Int): Int {
        val inorder = mutableListOf<Int>()
        inorderTraversal(root, inorder)
        return inorder[k - 1]
    }

    fun inorderTraversal(node: TreeNode?, inorder: MutableList<Int>) {
        if (node == null) return
        inorderTraversal(node.left, inorder)
        inorder.add(node.`val`)
        inorderTraversal(node.right, inorder)
    }
}

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

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    
    for {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        k--
        if k == 0 {
            return root.Val
        }
        
        root = root.Right
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def kth_smallest(root, k)
    result = []
    stack = []
    node = root
    
    while !node.nil? || !stack.empty?
        while !node.nil?
            stack.push(node)
            node = node.left
        end
        
        node = stack.pop
        result.push(node.val)
        return result[k-1] if result.length == k
        
        node = node.right
    end
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode 
= null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
  def kthSmallest(root: TreeNode, k: Int): Int = {
    def inorderTraversal(node: TreeNode, nums: List[Int]): List[Int] = {
      if (node == null) return nums
      inorderTraversal(node.left, node.value :: inorderTraversal(node.right, nums))
    }

    val inorder = inorderTraversal(root, List[Int]())
    inorder(k - 1)
  }
}

To solve this coding challenge, we need to find the kth smallest element in a Binary Search Tree (BST). Let's break down the problem and understand the solution methodology step-by-step. A Binary Search Tree (BST) is a binary tree where each node has at most two children. For each node, all elements in the left subtree are smaller, and all elements in the right subtree are larger. This property allows for an efficient way to handle operations like search, insert, and delete. To find the kth smallest element, we can leverage an Inorder Traversal of the BST. Inorder Traversal of a BST visits nodes in an ascending order (left-root-right). Thus, if we can maintain a counter during this traversal, the kth node encountered will be the kth smallest.

Explanation

Inorder Traversal : Inorder Traversal visits the left subtree, then the root node, and finally the right subtree. For a BST, this results in nodes being visited in ascending order.
Using a Stack : Instead of using recursion (which can lead to stack overflow for large trees), we will use an iterative approach with a stack. This allows us to handle deep trees more effectively and avoid the risk of running out of stack space.
Counter for k : We will maintain a counter that tracks how many nodes we have visited so far. When this counter reaches
k

, we know we've found the kth smallest element.
Edge Cases : The function needs to handle valid input constraints as specified. Given that constraints assure 1 <= k <= n <= 104, it's safe to assume the input
k

is always valid for the given tree.

Step-by-Step Explanation/Detailed Steps in Pseudocode

Declare a stack to manage our nodes to be visited .
Initialize the current node to the root of the tree .
Traverse the tree leftwards until we hit the end (null) :

Push the current node to the stack and move to its left child.

Pop the top node off the stack (this is the next node in inorder traversal):

Decrement the counter
k

as this is one of the nodes we are interested in.
Check if
k

is 0 - if it is, we have found our kth smallest node.

Move to the right subtree of the node we just visited.
Repeat the process until we find the kth node.

Pseudocode with Detailed Comments

                                            
# Define a method to find the kth smallest element in a BST
function kthSmallest(root, k):

    # Initialize an empty stack to store nodes
    stack = []

    # Continue until we've found the kth element
    while True:

        # Traverse the tree as deeply left as possible
        while root != null:
            # Push the current node onto the stack
            stack.append(root)
            # Move to the left child
            root = root.left

        # Backtrack: pop the last node added to the stack
        root = stack.pop()

        # Decrement k since we're visiting one more node in the inorder sequence
        k -= 1

        # If k becomes zero, we've found the kth smallest element
        if k == 0:
            # Return the value of the current node
            return root.val

        # Move to the right child of the node
        root = root.right

This pseudocode outlines the logic and gives a clear picture of how to approach the problem in an iterative manner using a stack. We handle each node exactly once and find the kth smallest element by counting down from k while performing an inorder traversal.