Reverse level order traversal of binary tree in python

Python program for Reverse level order traversal of binary tree. Here problem description and explanation.

``````#  Python 3 program for
#  Reverse level order traversal of binary tree
#  By using stack and queue

#  Binary Tree Node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

#  Create node of (Queue,Stack)
class Node :
def __init__(self, node) :
self.element = node
self.next = None

class MyQueue :
def __init__(self) :
self.tail = None
self.count = 0

def size(self) :
return self.count

def isEmpty(self) :
return self.count == 0

#  Add new node of queue
def enqueue(self, value) :
#  Create a new node
x = Node(value)
#  Add first element into queue
else :
#  Add node at the end using tail
self.tail.next = x

self.count += 1
self.tail = x

#  Delete a element into queue
def dequeue(self) :
#  Empty Queue
return

#  Visit next node
self.count -= 1
#  When deleting a last node of linked list
self.tail = None

#  Get front node
def peek(self) :
return None

#  Define a custom stack
class MyStack :
def __init__(self) :
self.top = None
self.count = 0

def size(self) :
return self.count

#  Add node at the top of stack
def push(self, element) :
#  Create new node
x = Node(element)
x.next = self.top
#  Make new top
self.top = x
self.count += 1

def isEmpty(self) :
if (self.size() > 0) :
return False
else :
return True

#  Remove top element of stack
def pop(self) :
if (self.size() > 0) :
#  Change top element of stack
self.top = self.top.next
self.count -= 1

def peek(self) :
if (self.size() == 0) :
return None

return self.top.element

class BinaryTree :
def __init__(self) :
self.root = None

def reverseLevelOrder(self) :
if (self.root != None) :
q = MyQueue()
s = MyStack()
q.enqueue(self.root)
node = self.root
while (q.isEmpty() == False and node != None) :
if (node.right != None) :
q.enqueue(node.right)

if (node.left != None) :
q.enqueue(node.left)

s.push(node)
#  Remove current node
q.dequeue()
node = q.peek()

#  Display result
while (s.isEmpty() == False) :
#  Get top element
node = s.peek()
#  Display level node
print(" ", node.data, end = " ")
#  Remove top
s.pop()

else :
print("Empty Tree")

def main() :
#  Create new tree
tree = BinaryTree()
#    Make A Binary Tree
#    -----------------------
#           1
#          / \
#         /   \
#        2     3
#       /     / \
#      4     5   6
#     /     / \   \
#    7     8   9   10
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(6)
tree.root.right.right.right = TreeNode(10)
tree.root.right.left = TreeNode(5)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(7)
tree.root.right.left.left = TreeNode(8)
tree.root.right.left.right = TreeNode(9)
#  Display the reverse level order elements
tree.reverseLevelOrder()

if __name__ == "__main__": main()``````

Output

``  7   8   9   10   4   5   6   2   3   1``

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.