Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order: 
	Left boundary nodes: defined as the path from the root to the left-most node ie- the leaf node you could reach when you always travel preferring the left subtree over the right subtree. 
	Leaf nodes: All the leaf nodes except for the ones that are part of left or right boundary.
	Reverse right boundary nodes: defined as the path from the right-most node to the root. The right-most node is the leaf node you could reach when you always travel preferring the right subtree over the left subtree. Exclude the root from this as it was already included in the traversal of left boundary nodes.
Note: If the root doesn't have a left subtree or right subtree, then the root itself is the left or right boundary. 
Example 1:
Input:
        1 
      /   \
     2     3  
    / \   / \ 
   4   5 6   7
      / \
     8   9
   
Output: 1 2 4 8 9 6 7 3
Explanation:
 
Example 2:
Input:
            1
           /
          2
        /  \
       4    9
     /  \    \
    6    5    3
             /  \
            7     8
Output: 1 2 4 6 5 7 8
Explanation:
As you can see we have not taken the right subtree. 
Your Task:
This is a function problem. You don't have to take input. Just complete the function boundary() that takes the root node as input and returns an array containing the boundary values in anti-clockwise.
Expected Time Complexity: O(N). 
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
1 ≤ Data of a node ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''

class Solution:

    def printBoundaryView(self, root):

        # Code here



Solutions:
class Solution:

	def printBoundaryView(self, root):
		if not root:
			return []
		left_bound = []
		bottom_bound = []
		right_bound = []
		runner = root
		if runner.left:
			while runner:
				left_bound.append(runner.data)
				if runner.left:
					runner = runner.left
				else:
					runner = runner.right
		runner = root

		def dfs(node):
			if not node:
				return
			if not node.left and (not node.right):
				bottom_bound.append(node.data)
			dfs(node.left)
			dfs(node.right)
		dfs(runner)
		runner = root
		if runner.right:
			while runner:
				right_bound.append(runner.data)
				if runner.right:
					runner = runner.right
				else:
					runner = runner.left
		if left_bound == [] and right_bound == []:
			return [root.data]
		elif left_bound == []:
			return [root.data] + bottom_bound[:] + right_bound[-2:0:-1]
		return left_bound + bottom_bound[1:] + right_bound[-2:0:-1]