Hi @dips !!
class Stack(object):
def __init__(self):
self.items = []
def __len__(self):
return self.size()
def size(self):
return len(self.items)
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def __str__(self):
s = ""
for i in range(len(self.items)):
s += str(self.items[i].value) + "-"
return s
class Queue(object):
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
if not self.is_empty():
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def peek(self):
if not self.is_empty():
return self.items[-1].value
def __len__(self):
return self.size()
def size(self):
return len(self.items)
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
def print_tree(self, traversal_type):
if traversal_type == "preorder":
return self.preorder_print(tree.root, "")
elif traversal_type == "inorder":
return self.inorder_print(tree.root, "")
elif traversal_type == "postorder":
return self.postorder_print(tree.root, "")
elif traversal_type == "levelorder":
return self.levelorder_print(tree.root)
elif traversal_type == "reverse_levelorder":
return self.reverse_levelorder_print(tree.root)
else:
print("Traversal type " + str(traversal_type) + " is not supported.")
return False
def preorder_print(self, start, traversal):
"""Root->Left->Right"""
if start:
traversal += (str(start.value) + "-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
def inorder_print(self, start, traversal):
"""Left->Root->Right"""
if start:
traversal = self.inorder_print(start.left, traversal)
traversal += (str(start.value) + "-")
traversal = self.inorder_print(start.right, traversal)
return traversal
def postorder_print(self, start, traversal):
"""Left->Right->Root"""
if start:
traversal = self.inorder_print(start.left, traversal)
traversal = self.inorder_print(start.right, traversal)
traversal += (str(start.value) + "-")
return traversal
def levelorder_print(self, start):
if start is None:
return
queue = Queue()
queue.enqueue(start)
traversal = ""
while len(queue) > 0:
traversal += str(queue.peek()) + "-"
node = queue.dequeue()
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return traversal
def reverse_levelorder_print(self, start):
if start is None:
return
queue = Queue()
stack = Stack()
queue.enqueue(start)
traversal = ""
while len(queue) > 0:
node = queue.dequeue()
stack.push(node)
if node.right:
queue.enqueue(node.right)
if node.left:
queue.enqueue(node.left)
while len(stack) > 0:
node = stack.pop()
traversal += str(node.value) + "-"
return traversal
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
print(tree.print_tree("reverse_levelorder"))
In the given code, the __str__()
method is overloaded in the Stack
class and the len()
method is overloaded in the Queue
class. Let’s understand their purpose and usage:
-
Overloading __str__()
method in Stack
class:
The __str__()
method in Python is used to define the string representation of an object. By overloading this method in the Stack
class, the code is customizing how the stack is represented as a string when print(tree.print_tree("reverse_levelorder"))
is called.
In the __str__()
method, a loop is used to iterate over each item in the stack and concatenate its value with a hyphen separator. This creates a string representation of the stack’s items in a specific format, where each item’s value is separated by a hyphen. The resulting string is then returned.
The purpose of overloading __str__()
in this case is to provide a readable representation of the stack’s items when printing the result of the reverse_levelorder_print()
method.
-
Overloading len()
method in Queue
class:
The len()
function in Python is used to get the length (number of items) of an object. In this case, the len()
method in the Queue
class is overloaded to provide the length of the queue by utilizing the size()
method.
The size()
method returns the length of the items
list, which represents the number of elements in the queue. By overloading len()
to call size()
, the code allows you to use the len()
function on a Queue
object to get its size.
The purpose of overloading len()
in this case is to provide a convenient way to get the size of the queue using the standard len()
function.
Overall, these overloading implementations provide custom behavior for string representation and length calculation for the Stack
and Queue
classes, respectively. They enhance the usability and readability of the code by providing appropriate representations and access to relevant information.
I hope it helps. Happy Learning