ProgramGuru.org

ProgramGuru.org

Find the kth Smallest Element in a Binary Search Tree

Visualization

Algorithm Steps

  1. Given a binary search tree (BST) and an integer k.
  2. Perform an in-order traversal of the BST, which visits nodes in ascending order.
  3. Keep a counter to track the number of nodes visited.
  4. When the counter equals k, record the current node's value as the kth smallest element.
  5. Return the recorded value as the result.

Find the kth Smallest Element in a BST - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.count = 0
        self.ans = None
        def inorder(node):
            if not node or self.ans is not None:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.ans = node.val
                return
            inorder(node.right)
        inorder(root)
        return self.ans

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #       3
    #      / \
    #     1   4
    #      \
    #       2
    root = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
    sol = Solution()
    print(sol.kthSmallest(root, 1))