878 · Boundary of Binary Tree

Dhanaraj S
3 min readApr 9, 2022

--

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

--

--

Dhanaraj S

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.