# Author: OMKAR PATHAK

# Depth first search is performed in three ways:

# Inorder

# Preorder

# Postorder

class Node(object):

def __init__(self, data = None):

self.left = None

self.right = None

self.data = data

# for setting left node

def setLeft(self, node):

self.left = node

# for setting right node

def setRight(self, node):

self.right = node

# for getting the left node

def getLeft(self):

return self.left

# for getting right node

def getRight(self):

return self.right

# for setting data of a node

def setData(self, data):

self.data = data

# for getting data of a node

def getData(self):

return self.data

# in this we traverse first to the leftmost node, then print its data and then traverse for rightmost node

def inorder(Tree):

if Tree:

inorder(Tree.getLeft())

print(Tree.getData(), end = ' ')

inorder(Tree.getRight())

return

# in this we first print the root node and then traverse towards leftmost node and then to the rightmost node

def preorder(Tree):

if Tree:

print(Tree.getData(), end = ' ')

preorder(Tree.getLeft())

preorder(Tree.getRight())

return

# in this we first traverse to the leftmost node and then to the rightmost node and then print the data

def postorder(Tree):

if Tree:

postorder(Tree.getLeft())

postorder(Tree.getRight())

print(Tree.getData(), end = ' ')

return

if __name__ == '__main__':

root = Node(1)

root.setLeft(Node(2))

root.setRight(Node(3))

root.left.setLeft(Node(4))

print('Inorder Traversal:')

inorder(root)

print('\nPreorder Traversal:')

preorder(root)

print('\nPostorder Traversal:')

postorder(root)

# OUTPUT:

# Inorder Traversal:

# 4 2 1 3

# Preorder Traversal:

# 1 2 4 3

# Postorder Traversal:

# 4 2 3 1