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