text: from binary_tree import Tree
  
  # dfs or left - right -mid
  def dfs_tree(tree):
      result = []
      stack = [tree.root]
      while len(stack):
          cur_node = stack.pop()
          if cur_node.right:
              stack.append(cur_node.right)
          if cur_node.left:
              stack.append(cur_node.left)
          result.append(cur_node.val)
  
      return result
  
  
  def lmr_tree(tree):
      result = []
      stack = [None]
      cur_node = tree.root
      while len(stack):
          if cur_node is not None:
              stack.append(cur_node)
              cur_node = cur_node.left
          else:
              cur_node = (
                  stack.pop()
              )  # pop from stack if reach end, where cur_node is None
              if cur_node is None:  # reach the end, where None marks the buttom of stack
                  break
              result.append(cur_node.val)
              cur_node = cur_node.right
  
      return result
  
  
  def unified_traversal_by_stack(
      tree, order="mlr"
  ):  # order can be m(id)l(eft)r(ight), lmr, rlm
      result = []
      stack = [tree.root]
      while len(stack):
          cur_node = stack.pop()
          if cur_node is None:
              cur_node = stack.pop()  # pop the node been marked processed by the None
              result.append(cur_node.val)
          else:
              for c in reversed(order):  # stack first in last out, so need to reverse it
                  if c == "m":
                      stack.append(cur_node)
                      stack.append(None)
                  if c == "l" and cur_node.left is not None:
                      stack.append(cur_node.left)
                  if c == "r" and cur_node.right is not None:
                      stack.append(cur_node.right)
  
      return result
  
  
  def unified_traversal_by_recursion(
      tree, order="mlr"
  ):  # order can be m(id)l(eft)r(ight), lmr, rlm
      result = []
  
      def traversal(node):
          for c in order:
              if c == "m":
                  result.append(node.val)
              if c == "l" and node.left is not None:
                  traversal(node.left)
              if c == "r" and node.right is not None:
                  traversal(node.right)
  
      traversal(tree.root)
  
      return result
  
  
  tree_data = [6, 5, 7, 3, 8, 4, 6.5, 1, 10]
  tree = Tree(tree_data)
  print("tree:", tree)
  print("dfs_traversal:", dfs_tree(tree))
  print("lmr_traversal:", lmr_tree(tree))
  print("mlr_traversal_stack_unified:", unified_traversal_by_stack(tree, "mlr"))
  print("lmr_traversal_stack_unified:", unified_traversal_by_stack(tree, "lmr"))
  print("lrm_traversal_stack_unified:", unified_traversal_by_stack(tree, "lrm"))
  
  print("mlr_traversal_recursive:", unified_traversal_by_recursion(tree, "mlr"))
  print("lmr_traversal_recursive:", unified_traversal_by_recursion(tree, "lmr"))
  print("lrm_traversal_recursive:", unified_traversal_by_recursion(tree, "lrm"))
  