educative.io

The provided solution is not correct!

Courses
#1

In the provided solution we skip nodes that are leafs when doing the level order traversal. How is that correct? What if that node is not only a leaf but also a node on the left side view then we will have an incorrect result. Consider this case as an example:
TreeNode root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(3);
root.left.right.left = new TreeNode(15);
root.left.right.left.left = new TreeNode(21);

When running the official solution this will give:
12 7 15 4 21 1 3

What would be expected is:
12 7 4 15 21 3 1

#2

Is it not the solution for your test case : 12,7,4,21,15,3,1

The solution mentioned in the course doesn’t seem to work for all the cases though.

#3

I agree. The solution offered does not work in some of the scenarios. Leftview should never be always the first part and right view should not be the last part in the result.
Sometimes the leaf node may be in the middle of left/right view.

Example 1:

           1
         /    \
       2        3
      / \      / \
    4   5     6   7
             /  \
            8    9
           /      \
          10      12

Expected result is: 1 2 4 5 8 10 12 9 7 3
8 appears in left view however it should be after the leaf node 5.

Example: 2

           1
         /    \
       2        3
      / \      / \
    4   5     6   7
       / \
      8   9
     /     \
   10       12

Expected result is: 1 2 4 8 10 12 9 6 7 3
9 appears in right view however it should be before the leaf node 6.

Have not yet sort out a solution.

#4

Here’s my Python solution that seems to work:

class Node:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

def tree_boundary2(root):
  if root is None:
    return ''

  left_set = set()
  right_set = set()

  boundary = []

  q = Queue()
  q.enq(root)

  while not(q.is_empty()):
    first_node = last_node = None
    next_level_nodes = []
    while not(q.is_empty()):
      node = q.deq()
      if first_node is None:
        first_node = node
      
      if node.left is not None:
        next_level_nodes.append(node.left)
      if node.right is not None:
        next_level_nodes.append(node.right)
    
    left_set.add(first_node)
    if node is not first_node:
      right_set.add(node)

    for node in next_level_nodes:
      q.enq(node)
  
  def dfs(node):
    added = False
    if node in left_set or (node.left is None and node.right is None):
      boundary.append(node)
      added = True
    
    if node.left is not None:
      dfs(node.left)
    if node.right is not None:
      dfs(node.right)
    
    if node in right_set and not(added):
      boundary.append(node)

  dfs(root)
  
  return ' -> '.join([str(node.val) for node in boundary])