Skip to main content

Reverse spiral traversal of a binary tree in

Vb program for Reverse spiral traversal of a binary tree. Here problem description and other solutions.

' Include namespace system
Imports System 
' program for
'  Reverse level order traversal in spiral form

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

'  Stack node
Public Class StackNode
    '  Stack data
    Public  element As TreeNode
    Public  [next] As StackNode
    Public Sub New(ByVal element As TreeNode, ByVal top As StackNode)
        Me.element = element = top
    End Sub
End Class

'  Define a custom stack
Public Class MyStack
    Public  top As StackNode
    Public  size As Integer
    Public Sub New()
        '  Set node values = Nothing
        Me.size = 0
    End Sub
    '  Add node at the top of stack
    Public Sub push(ByVal element As TreeNode) = New StackNode(element,
        Me.size += 1
    End Sub
    Public Function  isEmpty() As Boolean
        if (Me.size > 0 AndAlso IsNot Nothing) Then
            Return  False
            Return  True
        End IF
    End Function
    '  Remove top element of stack
    Public Sub pop()
        if (Me.size > 0 AndAlso IsNot Nothing) Then
            '  Change top element of stack
            Me.size -= 1
        End If
    End Sub
    '  Return top element of stack
    Public Function  peek() As TreeNode
        if (Me.size = 0) Then
            Return  Nothing
        End If
    End Function
End Class
public Class BinaryTree
    Public  root As TreeNode
    Public Sub New()
        '  Set initial tree root
        Me.root = Nothing
    End Sub
    '  Display tree element in reverse spiral level order traversal
    Public Sub reverseSpiral()
        if (Me.root  Is  Nothing) Then
            '  Case
            '  When empty
            Console.WriteLine("Empty Tree")
        End If
        '  Empty stack
        Dim s1 As MyStack = New MyStack()
        Dim s2 As MyStack = New MyStack()
        Dim result As MyStack = New MyStack()
        '  Some auxiliary variable
        Dim status As Integer = 1
        Dim node As TreeNode = Me.root
        '  Add first node
        while (node IsNot Nothing)
            '  Add node element into resultant stack
            if (status = 1) Then
                '  Add node from right to left
                '  in s2 stack
                if (node.right IsNot Nothing) Then
                    '  Add right child
                End If
                if (node.left IsNot Nothing) Then
                    '  Add left child
                End If
                '  Add node from left to right
                '  in s1 stack
                if (node.left IsNot Nothing) Then
                    '  Add left child
                End If
                if (node.right IsNot Nothing) Then
                    '  Add right child
                End If
            End IF
            if (status = 1) Then
                '  Case A
                '  When execute s1 stack
                '  Remove s1 element
                if (s1.isEmpty()) Then
                    '  When after remove s1 element
                    '  s1 stack empty.
                    '  Then change stack by s2
                    status = 2
                    '  Get first element of s2
                    node = s2.peek()
                    '  Otherwise get new top
                    node = s1.peek()
                End IF
                '  Case B
                '  When execute s2 stack
                '  Remove s2 element
                if (s2.isEmpty()) Then
                    '  Here change stack
                    status = 1
                    node = s1.peek()
                    node = s2.peek()
                End IF
            End IF
        End While
        '  Display final result
        while (result.isEmpty() = False)
            '  Get top element
            node = result.peek()
            '  Display node value
            Console.Write("   " +
            '  Remove top of stack
        End While
    End Sub
    Public Shared Sub Main(ByVal args As String())
        '  Create new tree
        Dim tree As BinaryTree = New BinaryTree()
        '   Make A Binary Tree
        '    ---------------
        '       1
        '      / \ 
        '     /   \
        '    2     3
        '   /     / \
        '  4     5   6
        '   \    \    \
        '    7    8    9
        '  Add node
        tree.root = New TreeNode(1)
        tree.root.left = New TreeNode(2)
        tree.root.right = New TreeNode(3)
        tree.root.right.right = New TreeNode(6)
        tree.root.right.left = New TreeNode(5)
        tree.root.left.left = New TreeNode(4)
        tree.root.left.left.right = New TreeNode(7)
        tree.root.right.left.right = New TreeNode(8)
        tree.root.right.right.right = New TreeNode(9)
        '  Display reverse spiral level order element
    End Sub
End Class


   9   8   7   4   5   6   3   2   1


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