educative.io

One-pass solution

Courses
,
#1

The problem can be solved in one traverse over the tree if you pass additional signs to the function. I pass left and right flags to indicate if I go along the left edge or right edge:

def display_tree_perimeter(root):
  result = ""
  stack_right = []
  def walk_and_print(root, left, right):
    nonlocal result
    this_was_printed = False
    if root.left:
      if left:
        if not this_was_printed:
          result += str(root.data) + " "
          this_was_printed = True
        walk_and_print(root.left, True, False)
      else:
        walk_and_print(root.left, False, False)
    if root.right:
      if right:
        if not this_was_printed:
          stack_right.append(root.data)
          this_was_printed = True
        walk_and_print(root.right, False, True)
      else:
        walk_and_print(root.right, False, False)
    if root.left is None and root.right is None:
      if not this_was_printed:
        result += str(root.data) + " "
        this_was_printed = False
  walk_and_print(root, True, True)
  while stack_right:
    result += str(stack_right.pop()) + " "
  return result
1 Like
#2

nice solution, I did something similar but slightly different
you can just do an in-order traversal with the following conditional logic

take the root always
if you’ve only gone left and not right then it’s on the left perimeter
else if you’ve only gone right and not left then it’s on the left perimeter
else (you’ve implicitly gone both left and right) if the node has no left or right then it’s on the bottom

but I like your solution better since it doesn’t require keeping track of these three components separately then re-compiling root + reversed(left) + bottom + reversed(right)

Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers