fork download
copy 
  1.  
  2. class Node:
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right
  7.  #            10
  8.  #         /      \
  9.  #        /        \
  10.  #       /          \
  11.  #      5           15
  12.  #    /   \       /    \
  13.  #   3     8     13      20
  14.  #  / \   /  \  /  \    /  \
  15.  # 1   4  6  9  11  14  17  25
  16.  
  17.  
  18. def buildTree():
  19.     n17 = Node(val=17)
  20.     n25 = Node(val=25)
  21.     n20 = Node(val=20, left=n17, right=n25)
  22.  
  23.     n11 = Node(val=11)
  24.     n14 = Node(val=14)
  25.     n13 = Node(val=13, left=n11, right=n14)
  26.  
  27.     n15 = Node(val=15, left=n13, right=n20)
  28.  
  29.     n6 = Node(val=6)
  30.     n9 = Node(val=9)
  31.     n8 = Node(val=8, left=n6, right=n9)
  32.  
  33.     n4 = Node(val=4)
  34.     n1 = Node(val=1)
  35.     n3 = Node(val=3, left=n1, right=n4)
  36.  
  37.     n5 = Node(val=5, left=n3, right=n8)
  38.  
  39.     n10 = Node(val=10, left=n5, right=n15)
  40.  
  41.     return n10
  42.  
  43.  
  44. class LazyExplicitStackBasedExplorer:
  45.     def __init__(self, root):
  46.         self.stack = []
  47.         self.current_node = root
  48.         self.next_value = None
  49.  
  50.     def get_next_value(self):
  51.         if self.current_node is not None or len(self.stack) > 0:
  52.             self.visit_next_node()
  53.             return self.next_value
  54.         else:
  55.             return None
  56.  
  57.     def visit_next_node(self):
  58.         while self.current_node is not None:
  59.             self.stack.append(self.current_node)
  60.             self.current_node = self.current_node.left
  61.  
  62.         self.current_node = self.stack.pop()
  63.         self.next_value = self.current_node.val
  64.         self.current_node = self.current_node.right
  65.  
  66.  
  67. class LazyGeneratorBasedExplorer:
  68.     def __init__(self, root):
  69.         self.iterator = self.visit_next_node(root)
  70.  
  71.     def get_next_value(self):
  72.         try:
  73.             return next(self.iterator)
  74.         except StopIteration:
  75.             return None
  76.  
  77.     def visit_next_node(self, root):
  78.         if root.left is not None:
  79.             for value in self.visit_next_node(root.left):
  80.                 yield value
  81.  
  82.         yield root.val
  83.  
  84.         if root.right is not None:
  85.             for value in self.visit_next_node(root.right):
  86.                 yield value
  87.  
  88.  
  89. if __name__ == '__main__':
  90.     root = buildTree()
  91.     # explorer = LazyExplicitStackBasedExplorer(root)
  92.     explorer = LazyGeneratorBasedExplorer(root)
  93.  
  94.     while True:
  95.         val = explorer.get_next_value()
  96.  
  97.         if val is None:
  98.             break
  99.  
  100.         print(val)
Success #stdin #stdout 0.03s 8960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
3
4
5
6
8
9
10
11
13
14
15
17
20
25
https://ideone.com/G4yyAd
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!