# 878 · Boundary of Binary Tree

--

Given a binary tree, return the values of its boundary in **anti-clockwise** direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.

**Left boundary** is defined as the path from root to the **left-most** node. **Right boundary** is defined as the path from root to the **right-most** node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The **left-most** node is defined as a **leaf** node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The **right-most** node is also defined by the same way with left and right exchanged.

**Example 1:**

`Input: {1,#,2,3,4}`

Output: [1,3,4,2]

Explanation:

1

\

2

/ \

3 4

The root doesn't have left subtree, so the root itself is left boundary.

The leaves are node 3 and 4.

The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.

So order them in anti-clockwise without duplicates and we have [1,3,4,2].

**Example 2:**

`Input: {1,2,3,4,5,6,#,#,#,7,8,9,10}`

Output: [1,2,4,7,8,9,10,6,3]

Explanation:

1

/ \

2 3

/ \ /

4 5 6

/ \ / \

7 8 9 10

The left boundary are node 1,2,4. (4 is the left-most node according to definition)

The leaves are node 4,7,8,9,10.

The right boundary are node 1,3,6,10. (10 is the right-most node).

So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

Solution:

The approach is simple.*step 1:*

Traverse the left sub-tree except leaf nodes and add those nodes in to the result.

In this traversal we go on traversing the left child and if the left is null we go to right child. Also note the edge case where the immediate left child of the root can be null. In this case we should not go to right child , even though the left child is null. That is why we compare if the current node is the start or root node in the elif condition.

*step 2:*

Traverse the tree preorder and add the leaf nodes to the result

*step 3:*

Traverse the right subtree except leaf nodes and add those nodes in reverse order to the result(also note to pop the root from the reversed list , as this is covered in the step 1)

In this traversal we go on traversing the right child and if the right is null we go to left child. Also note the edge case where the immediate right child of the root can be null. In this case we should not go to left child , even though the right child is null. That is why we compare if the current node is the start or root node, in the elif condition .

Solution

class Solution:

def left_func(self,left,root):

temp=root

while(temp):

left.append(temp.val)

if temp.left == None and temp.right ==None:

temp=temp.left

left.pop(-1)

elif temp.left or temp==self.start:

temp=temp.left

else:

temp=temp.right

def preorder(self,leaf,temp):

if temp==None:

return

if temp.left == None and temp.right ==None:

leaf.append(temp.val)

self.preorder(leaf,temp.left)

self.preorder(leaf,temp.right)

def right_func(self,right,root):

temp=root

while(temp):

right.append(temp.val)

if temp.left == None and temp.right ==None:

temp=temp.right

right.pop(-1)

elif temp.right or temp==self.start:

temp=temp.right

else:

temp=temp.left def boundary_of_binary_tree(self, root):

self.left_arr=[]

self.leafs=[]

self.right_arr=[]

self.start = root

arr=[]

self.left_func(self.left_arr , root)

self.preorder(self.leafs,root)

self.right_func(self.right_arr,root) arr.extend(self.left_arr)

arr.extend(self.leafs)

self.right_arr=self.right_arr[::-1]

if self.right_arr:

self.right_arr.pop(-1)

arr.extend(self.right_arr)

return arr

*Time :O(N)*

*Space:O(N)*

The above algorithm , written in a clean code aspect.

class Solution:

def left_func(self,res,root):

temp=root.left

while(temp):

if temp.left != None or temp.right !=None:

res.append(temp.val)

if temp.left:

temp=temp.left

else:

temp=temp.right

def preorder(self,res,temp):

if temp.left == None and temp.right ==None:

res.append(temp.val)

return

if temp.left :

self.preorder(res,temp.left)

if temp.right:

self.preorder(res,temp.right)

def right_func(self,res,root):

temp=root.right

temporary=[]

while(temp):

if temp.left != None or temp.right !=None:

temporary.append(temp.val)

if temp.right:

temp=temp.right

else:

temp=temp.left

for i in range(len(temporary)-1,-1,-1):

res.append(temporary[i])

def boundary_of_binary_tree(self, root):

arr=[]

if root:

# tree has just a leaf node,

if root.left == None and root.right == None:

return [root.val]

arr.append(root.val)

self.left_func(arr , root)

self.preorder(arr,root)

self.right_func(arr,root)

return arr