Skip to main content

Inorder traversal of binary tree using stack in vb.net

Vb program for Inorder traversal of binary tree using stack. Here problem description and explanation.

' Include namespace system
Imports System 
'  Vb.net program for
'  Inorder traversal without recursion
'  Using stack

'  Binary Tree node
Public Class TreeNode 
    Public  data As Integer
    Public  left As TreeNode
    Public  right As TreeNode
    '  Make a tree node
    Public Sub New(ByVal data As Integer)
        
        '  Set node data
        Me.data = data
        Me.left = Nothing
        Me.right = Nothing
    
    End Sub

End Class
Public Class StackNode 
    Public  element As TreeNode
    Public  [next] As StackNode
    Public Sub New(ByVal element As TreeNode)
        Me.element = element
        Me.next = Nothing
    End Sub

End Class'  Stack Class
Public Class MyStack 
    Public  top As StackNode
    Public  size As Integer
    
    Public Sub New()
        
        Me.top = Nothing
        Me.size = 0
    
    End Sub
    '  Add new element into stack
    Public Sub push(ByVal element As TreeNode)
        '  Create new node
        Dim node As StackNode = New StackNode(element)
        node.[next] = Me.top
        '  new node is new top
        Me.top = node
        '  Increase the size
        Me.size += 1
    
    End Sub
    '  Remove top element of the stack
    Public Sub pop()
        if (Me.top IsNot Nothing) Then 
            '  next node is new top
            Me.top = Me.top.[next]
            '  Reduce size
            Me.size -= 1
        End If

    
    End Sub
    '  Returns the status of empty or non empty stacks
    Public Function  isEmpty() As Boolean
        if (Me.size > 0 AndAlso Me.top IsNot Nothing) Then 
            Return False
        Else 
            Return True
        End IF

    End Function 
    
    '  Return top element of stack
    Public Function  peek() As TreeNode
        if (Me.isEmpty()) Then 
            Return Nothing
        End If

        Return Me.top.element
    End Function 

End Class
public Class BinaryTree 
    Public  root As TreeNode
    
    Public Sub New()
        '  Set initial tree root to null
        Me.root = Nothing
    
    End Sub
    '  Display Inorder view of binary tree
    
    Public Sub inorder()
        if (Me.root IsNot Nothing) Then 
            '  Make new stack
            Dim s As MyStack = New MyStack()
            Dim node As TreeNode = Me.root
            '  Display tree element
            
            while (Not s.isEmpty() OrElse node IsNot Nothing) 
            
                if (node IsNot Nothing) Then 
                    '  Add current node
                    s.push(node)
                    '  Visit to left subtree
                    node = node.left
                Else 
                    '  When node is null
                    '  Get stack top element
                    node = s.peek()
                    '  Display node value
                    Console.Write(" " + node.data.ToString())
                    '  Remove top element of the stack
                    s.pop()
                    '  Visit to left subtree of current node
                    node = node.right
                End IF

            End While
        Else 
            Console.Write("Empty Linked List" & vbLf )
        End IF

    
    End Sub
    
    Public Shared Sub Main(ByVal args As String())
        '  Create new tree
        Dim tree As BinaryTree = New BinaryTree()
        '    Construct Binary Tree
        '    -----------------------
        '        15
        '       /  \
        '      24   54
        '     /    /  \
        '    35   62   13
        '  Add tree nodes
        tree.root = New TreeNode(15)
        tree.root.left = New TreeNode(24)
        tree.root.right = New TreeNode(54)
        tree.root.right.right = New TreeNode(13)
        tree.root.right.left = New TreeNode(62)
        tree.root.left.left = New TreeNode(35)
        '  Display result
        tree.inorder()
    
    End Sub

End Class

Output

 35 24 15 62 54 13




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.

New Comment