Amazon interview question

Someone posted this on http://discuss.techinterview.org/cursor.gif


You are given a threaded binary tree where each node of a tree points to some node to the right of it in in-order traversal. Given such tree, check whether each thread pointer of the node in a tree satisfies this condition( i.e check whether if thread pointer is pointing to node that is on the right side in in-order traversal). If not make that pointer NULL else leave it.Each node has only three pointers pointing to left, right nodes and other the thread pointer. Space and Time constraint has to be considered while designing it.
IvflyMay 5, 2009

.. this little snippet should do the trick ....

Option Strict On
Option Explicit On

Public Class TNode
Private left As TNode
Private right As TNode
Private rightInOrder As TNode
Private name As String

'''

''' Returns the next node to the right of this node in an in-order traversal
''' This will be the leftmost node of the subtree of the right child.
'''

Private Function nextRight() As TNode
If right Is Nothing Then
Return Nothing
End If
Return right.leftMost()
End Function
'''

''' Returns the leftmost child of this subtree
'''

Private Function leftMost() As TNode
If left Is Nothing Then
Return Me
End If
Return left.leftMost()
End Function

Function validateTree() As Boolean
If (nextRight() Is rightInOrder) Then
Console.WriteLine("Node {0} is correct", name)
Else
rightInOrder = Nothing
End If
If Not left Is Nothing Then
left.validateTree()
End If
If Not right Is Nothing Then
right.validateTree()
End If
End Function
End Class

Module Module1
Sub Main()
' call with root
End Sub
End Module