Find kth smallest element in BST vb.net

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

``````' Include namespace system
Imports System
'  Vb.net 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)
Me.data = 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 (node.data >= data) Then
'  When new element is smaller or equal to current node
node.left = Me.insert(node.left, data)
Else
'  When new element is higher to current node
node.right = Me.insert(node.right, data)
End IF
'  Important to manage new node
Return  node
Else
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
Return
End If
if (Me.element  Is  Nothing OrElse
Me.element.data < node.data) 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")
Else
'  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 " +
Me.counter.ToString())
Else
Console.WriteLine("[" + k.ToString() +
"] smallest node : " +
Me.element.data.ToString())
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
'  Testing
tree.printKthSsmallest(6)
tree.printKthSsmallest(4)
tree.printKthSsmallest(3)
End Sub
End Class``````

Output

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

Comment

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.