1  from typing import List
  2  from eg_deque import Deque
  3  
  4  
  5  class BSTNode:
  6      def __init__(self, x, left=None, right=None):
  7          self.val, self.left, self.right = x, left, right
  8  
  9  
 10  def level_order(root: BSTNode) -> List[int]:
 11      traversal = []
 12      queue = Deque()
 13      queue.enqueue(root)
 14      while queue.size > 0:
 15          node = queue.dequeue()
 16          traversal.append(node.val)
 17          if node.left is not None:
 18              queue.enqueue(node.left)
 19          if node.right is not None:
 20              queue.enqueue(node.right)
 21      return traversal
 22  
 23  
 24  def pre_order(root: BSTNode) -> List[int]:
 25      traversal = []
 26      stack = Deque()
 27      stack.push(root)
 28      while stack.size > 0:
 29          node = stack.pop()
 30          traversal.append(node.val)
 31          if node.right is not None:
 32              stack.push(node.right)
 33          if node.left is not None:
 34              stack.push(node.left)
 35      return traversal
 36  
 37  
 38  def in_order(root: BSTNode) -> List[int]:
 39      traversal = []
 40      stack = Deque()
 41      cur = root
 42      while cur is not None or stack.size > 0:
 43          if cur is not None:
 44              stack.push(cur)
 45              cur = cur.left
 46          else:
 47              cur = stack.pop()
 48              traversal.append(cur.val)
 49              cur = cur.right
 50      return traversal
 51  
 52  
 53  def post_order(root: BSTNode) -> List[int]:
 54      s1, s2 = Deque(), Deque()
 55      s1.push(root)
 56      while s1.size > 0:
 57          node = s1.pop()
 58          s2.push(node)
 59          if node.left is not None:
 60              s1.push(node.left)
 61          if node.right is not None:
 62              s1.push(node.right)
 63  
 64      traversal = []
 65      while s2.size > 0:
 66          traversal.append(s2.pop().val)
 67      return traversal
 68  
 69  
 70  def zig_zag(root: BSTNode) -> List[int]:
 71      pass
 72  
 73  
 74  """ ========== Testing BST ========== """
 75  # Example from: geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
 76  
 77  def test_bst():
 78      n4 = BSTNode(4)
 79      n12 = BSTNode(12)
 80      n18 = BSTNode(18)
 81      n24 = BSTNode(24)
 82      n31 = BSTNode(31)
 83      n44 = BSTNode(44)
 84      n66 = BSTNode(66)
 85      n90 = BSTNode(90)
 86  
 87      n10 = BSTNode(10, n4, n12)
 88      n22 = BSTNode(22, n18, n24)
 89      n35 = BSTNode(35, n31, n44)
 90      n70 = BSTNode(70, n66, n90)
 91  
 92      n15 = BSTNode(15, n10, n22)
 93      n50 = BSTNode(50, n35, n70)
 94  
 95      r = BSTNode(25, n15, n50)
 96  
 97      # print(level_order(r))
 98      # print(pre_order(r))
 99      # print(in_order(r))
100      print(post_order(r))
101  
102  
103  test_bst()