Skip to main content

Inorder traversal of binary tree using stack in

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

' Include namespace system
Imports System 
' 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 = 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 = Nothing
    End Sub

End Class'  Stack Class
Public Class MyStack 
    Public  top As StackNode
    Public  size As Integer
    Public Sub New()
        = 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] =
        '  new node is new top = node
        '  Increase the size
        Me.size += 1
    End Sub
    '  Remove top element of the stack
    Public Sub pop()
        if ( IsNot Nothing) Then 
            '  next node is new top
            '  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 IsNot Nothing) Then 
            Return False
            Return True
        End IF

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

    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
                    '  Visit to left subtree
                    node = node.left
                    '  When node is null
                    '  Get stack top element
                    node = s.peek()
                    '  Display node value
                    Console.Write(" " +
                    '  Remove top element of the stack
                    '  Visit to left subtree of current node
                    node = node.right
                End IF

            End While
            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
    End Sub

End Class


 35 24 15 62 54 13


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