Skip to main content

Find kth smallest element in BST

Find the kth smallest node in binary tree

Vb program for Find kth smallest element in BST. Here mentioned other language solution.

' Include namespace system
Imports System 
' program for
'  K’th smallest element in Binary Search Tree
Public Class TreeNode
    Public  data As Integer
    Public  left As TreeNode
    Public  right As TreeNode
    Public Sub New(ByVal data As Integer) = data
        Me.left = Nothing
        Me.right = Nothing
    End Sub
End Class

public Class BinarySearchTree
    Public  root As TreeNode
    Private counter As Integer
    Private element As TreeNode
    Public Sub New()
        Me.root = Nothing
    End Sub
    '  Insert a node element
    Public Function  insert(ByVal node As TreeNode, 
                            ByVal data As Integer) As TreeNode
        if (node IsNot Nothing) Then
            if ( >= data) Then
                '  When new element is smaller or equal to current node
                node.left = Me.insert(node.left, data)
                '  When new element is higher to current node
                node.right = Me.insert(node.right, data)
            End IF
            '  Important to manage new node
            Return  node
            Return  New TreeNode(data)
        End IF
    End Function
    '  Find the kth smallest node in BST
    Public Sub findKthSmallest(ByVal node As TreeNode, 
                               ByVal k As Integer)
        if (node IsNot Nothing) Then
            '  Visit left subtree
            Me.findKthSmallest(node.left, k)
            if (Me.counter = k) Then
                '  Stop recursion
            End If
            if (Me.element  Is  Nothing OrElse 
       < Then
                '  Modified counter variable by one
                Me.counter += 1
                '  Collect possible result
                Me.element = node
            End If
            '  Visit right subtree
            Me.findKthSmallest(node.right, k)
        End If
    End Sub
    Public Sub printKthSsmallest(ByVal k As Integer)
        if (k <= 0) Then
            '  When given k is not valid positive values
            Console.WriteLine("Invalid node position " + k.ToString())
        ElseIf (Me.root  Is  Nothing) Then
            '  When BST are no have elements
            Console.WriteLine("Empty Binary Search Tree")
            '  Reset values
            Me.counter = 0
            Me.element = Nothing
            '  Find result
            Me.findKthSmallest(Me.root, k)
            if (Me.counter < k) Then
                '  If In case given kth smallest node are
                '  Not exist in binary search tree, then
                Console.WriteLine("Given " + k.ToString() + 
                                  " smallest node are not exist " + 
                Console.WriteLine("[" + k.ToString() + 
                                  "] smallest node : " + 
            End IF
        End IF
    End Sub
    '  Handle request to add new node
    Public Sub addNode(ByVal key As Integer)
        Me.root = Me.insert(Me.root, key)
    End Sub
    Public Shared Sub Main(ByVal args As String())
        Dim tree As BinarySearchTree = New BinarySearchTree()
        '    Make Tree
        '    ----------
        '        7
        '       / \ 
        '      /   \
        '     4     9
        '    / \   / \
        '   3   5 8   10
        '      /    
        '     4     
        '  Add node
        '  Testing
    End Sub
End Class


[6] smallest node : 9
[4] smallest node : 7
[3] smallest node : 5


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment