Basics: Full Search of Tree Structure (DFS/BFS)

Self-introduction

Nice to meet you. Thank you for visiting this magazine. I have been doing FAE (Technical Sales) for semiconductors (FPGA/DCDC) for 12 years. Technical sales are not limited to selling products together with sales Our business is technical support (answering technical questions about products) and troubleshooting (device defects). Since I often go out with debugging in the name of a device failure, Almost anything shop that supports both soft and hard aspects.

I started python programming as a hobby. Since the business FPGA used Verilog and VHDL to handle the program language. I enjoy playing python as an extension of my hobby, but I'm not a developer, so I'm an amateur. I started leetcode to test my strength.

The wall I faced immediately

I'm not proud, but I'm an amateur. There is no foundation. When I challenge leetcode, the action policy is ** Build an algorithm from 0 in your head and write a program !! ** Only this one point breakthrough.

This course of action may have the benefit of developing thinking skills, I feel that there are more disadvantages. The disadvantages I think are: ** 1. I try to assemble from 0 in my own way, so it takes time anyway! 2. Anyway, there are many useless descriptions in my own style 3. The more descriptions, the more mistakes 4. If your brain is not in top gear, you may not be able to solve problems that you have solved in the past **

That is, the processing time is long and the output is not stable. There is nothing good about it.

By learning the basics firmly and challenging the problem based on the absorbed basic form I decided to take on my own challenge to shorten the processing time and stabilize the output. This magazine is the record. Of course, a loving plunge is welcome.

Definition of foundation

This time, it is based on ** Leetcode: Explorer Binary Tree **. The policy is to ** remember the basic form and understand the behavior **. Since the example is defined as the basis, I think that the operation image will be a way of thinking that can be applied to everything.

For the practice of exploration, we will proceed with the story based on the following binary search tree that was also made as a review. (Node deletion is omitted).

BinTree.py

#The description is not related to the binary search tree,
#Deque when exploring()Because it uses
from collections import deque 

#Definition of node
class node:
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

class BinTree:
    #self.Create a tree based on root, initial value None
    def __init__(self):
        self.root = None
        
    def add(self,val):
       #The following def add_Skip node and go to the comment at the bottom!
        def add_node(root,val):
            if val < root.val:
                if not root.left:
                    root.left = node(val)
                else:
                    add_node(root.left,val)
            if val > root.val:
                if not root.right:
                    root.right = node(val)
                else:
                    add_node(root.right,val)

       #def add()The first program to run in.
       #First self.Check if root is None
       #If None, call node and assign val
        if not self.root:
            self.root = node(val)
       #add if not None_call node
        else:
            add_node(self.root,val)        

####Tree_image#####
#         4       #
#      /     \    #
#     2       6   #
#    / \     /    # 
#   1   3   5     # 
###################

T = BinTree()  #self.Create root
T.add(4)
T.add(2)
T.add(3)
T.add(1)
T.add(6)
T.add(5)

To briefly supplement, in order to establish it as a binary search tree I think the description of def add_node () embedded in def add () is a miso. Whether it is greater than or less than the value of the branch source each time it branches as a node Because you need to judge.

Search method

According to leetcode, the search method is DFS: Pre-order/In-order/Post-order, BFS. The figure below is an image of each approach. The number assigned to each node is the search order. It is very difficult to imagine a program just by looking at this figure. In this magazine, you will understand and remember the basic form from the examples. We will proceed with the policy of practicing whether the basic form can be rearranged and applied.

Example 1 DFS: Preorder/Inorder/Postorder

`Search the binary search tree and return a value on each node. However, use three search approaches: Preorder/Inorder/Postorder. ``

Answer_Sample_Preorder.py

Input: root = [4,2,6,1,3,5]
Output:4      #-----Tree_image---#
       2      #         4        #
       1      #      /     \     #
       3      #     2       6    #
       6      #    / \     /     #
       5      #   1   3   5      #
              #------------------#

[Restrictions] -Tree elements consist of 0 ~ 100 ・ -100 <= node.val <= 100

Commentary

This is an example, so I don't know. Let's go with the following flow.

** 1. Suddenly read the answer 2. Image the operation 3. Match the answers with a separately prepared GIF **

Now, the answer is here. Learn the three patterns of Preorder/Inorder/Postorder approaches.

TreeDFS.py

def DFS(self):                      
    def pre_order(node):            
        print(node.val)             
        if node.left:pre_order(node.left)    
        if node.right:pre_order(node.right)   

    def in_order(node):
        if node.left: in_order(node.left)
        print(node.val)
        if node.right: in_order(node.right)

    def post_order(node):
        if node.left: post_order(node.left)
        if node.right: post_order(node.right)
        print(node.val)
    #-----------------------#
    #--select DFS approach--#
    #-----------------------#
    #1 preorder
    return pre_order(self.root)
    
    #2 inorder
    #return in_order(self.root)
    
    #3 postorder
    #return post_order(self.root)

As you can see, there is almost no difference in the description of Preorder/Inorder/Postorder. Let's make an image while reading, I think it's okay to make a mistake.

Let's check if there are any omissions in the created image. Click on the GIF below to enlarge it for clarity. If you can print everything with print (), it's not the end You can deepen your understanding by following the process to the end and confirming that it is completed.

I considered another approach just in case, but I think there are other smart descriptions. I'm sorry for sharing at this level now.

TreeDFS.py

#Preorder
def DFS(self):
   buff = [self.root]
   while buff:
       nums = buff.pop()
       print(nums.val)
       if nums.right: buff.append(nums.right)
       if nums.left: buff.append(nums.left)

"""
#Inorder
def DFS(self):
   B0 = deque([self.root])
   B1 = []
       
   root = B0.popleft()
   while root or B1:
       while root:
           B1.append(root)
           root = root.left
       root = B1.pop()
       print(root.val)
       root = root.right
"""

"""
#Postorder
def DFS(self):
   buff,ans=deque([self.root]),deque([])
   while buff:
       nums = buff.pop()
       ans.appendleft(nums.val)
       if nums.left:buff.append(nums.left)
       if nums.right:buff.append(nums.right)
   for i in range(len(ans)):
       print(ans[i])
"""

Now that you're ready, challenge Leetcode.

Exercise 1 Binary Tree Preorder/Inorder/Postorder

`Search the binary search tree and list and return each node. However, use three search approaches: Preorder/Inorder/Postorder. ``

Answer_Image.py

Input: root = [4,2,6,1,3,5]
Output: [4,2,1,3,6,5]

[Restrictions] -Tree elements consist of 0 ~ 100 ・ -100 <= node.val <= 100

Commentary

Let's do something with the uninflected word that we solved (or remembered) in Example 1. However, I think it is difficult to solve the exercise with a round copy of the example.

When solving with recursive processing, enter from the beginning of the function and If you return to the beginning of the function again with return, the definition of [] for output gets in the way. For example, if you define ans = [], you can recursively return to the beginning. Since it is always initialized as ans = [], the calculated value cannot be accumulated.

I couldn't find a countermeasure for myself now, so This time, I tried to embed def inside def.

Preorder_list.py

def DFS(self):
   ans = []
   def preorder(node,ans):
      ans.append(node.val)
      if node.left: preorder(node.left,ans)
      if node.right: preorder(node.right,ans)
      return ans
   return preorder(self.root,ans)

As mentioned above, prepare a preorder in DFS, It is recursively processed by preorder. Be sure to take the ans that stores node.val to the next hierarchy It is preorder (node.left, ** ans **).

As many of you may know, this ** ans ** can actually be omitted. Almost the same, but the same output can be obtained with the following description.

Preorder_list.py

def DFS(self):
   ans = []
   def preorder(node):
      ans.append(node.val)
      if node.left: preorder(node.left)
      if node.right: preorder(node.right)
      return ans
   
   def inorder(node):
      if node.left: preorder(node.left)
      ans.append(node.val)
      if node.right: preorder(node.right)
      return ans

   def postorder(node):
      if node.left: preorder(node.left)
      if node.right: preorder(node.right)
      ans.append(node.val)
      return ans

    #-----------------------#
    #--select DFS approach--#
    #-----------------------#
    #1 preorder
    return pre_order(self.root)
    
    #2 inorder
    #return in_order(self.root)
    
    #3 postorder
    #return post_order(self.root)

Another point is return. If you don't notify the caller of ans with node.val added, The final output cannot be achieved by picking up all the elements. Just in case, I made a GIF and checked if there was a lie in my explanation (laughs). Since the basics of Inorder/Postorder are the same, I don't think GIF is necessary, but I will consider it if requested.

Example 2 BFS

`Search the binary search tree, search each node with BFS, and return the value. ``

Answer_Image.py

Input: root = [4,2,6,1,3,5]
Output:4      #-----Tree_image---#
       2      #         4        #
       6      #      /     \     #
       1      #     2       6    #
       3      #    / \     /     #
       5      #   1   3   5      #
              #------------------#

[Restrictions] -Tree elements consist of 0 ~ 100 ・ -100 <= node.val <= 100

Commentary

Sorry for the same problem as in Example 1. DFS and BFS are separated because the basic approach is completely different. Separated to avoid confusion. First of all, I will share the image of BFS. From this image, we can see that BFS is realized by buffering the data collectively for each layer. Here's how to do that.

TreeBFS.py

def BFS(self):
    q = [self.root]
    def left2right(q):
        laylength = len(q)
        for _ in range(laylength):
            nums = q.pop(0)
            print(nums.val)
            if nums.left:q.append(nums.left)
            if nums.right:q.append(nums.right)
        if laylength > 0:left2right(q)
    return left2right(q)

As per the code, Buffer the nums.left / nums.right contained in the retrieved nums.val into q. Since the above work is repeated laylength (= len (q)) times, As a result, the data of the same layer can be collectively buffered in q. Of course, q may be mixed with data from other layers, Since the for minute only turns the for for laylength times, We do not manage to extract extra data from other layers.

Exercise 2 Binary Tree Level Order Traversal

`Search the binary search tree and list it in each layer. ``

Answer_Image.py

Input: root = [4,2,6,1,3,5]
Output:[          #-----Tree_image---#
        [4],      #         4        #
        [2,6],    #      /     \     #
        [1,3,5],  #     2       6    #
       ]          #    / \     /     #
                  #   1   3   5      #
                  #------------------#

Commentary

In the example above, all elements are buffered in q, BFS was established because the elements were uprooted and buffered for each layer and output. For example, if the process of turning with for can be numbered as 1st layer, 2nd layer, 3rd layer ..etc, I think that the problem can be solved because append () can be done for each layer. Here is the idea.

TreeBFS.py

def BFS(self):
    q = deque([self.root])
    ans = []
    level = 0
    def helper(q,level):
         ans.append([])
         laylength = len(q)
         for _ in range(laylength):
             nums = q.popleft()
             ans[level].append(nums.val)
             if nums.left:q.append(nums.left)
             if nums.right:q.append(nums.right)
         if len(q) > 0:helper(q,level+1)
         return ans
     return helper(q,level)

#def BFS(self):
#        q = deque([self.root])
#        level = 0
#        ans = []
#        while q:
#            ans.append([])
#            laylength = len(q)
#            for _ in range(laylength):
#                nums = q.popleft()
#                ans[level].append(nums.val)
#                if nums.left:q.append(nums.left)
#                if nums.right:q.append(nums.right)
#            level += 1
#        return ans

I posted another approach in the comment out, but personally I prefer not recursive processing I feel that I can write simply about this matter.

There are other approaches besides the above. I tried DFS version.

TreeDFS.py

def DFS(self):
    ans = []
    level = 0                      
    def pre_order(node,level):            
        if len(ans)==level:
            ans.append([])
        ans[level].append(node.val)            
        if node.left:pre_order(node.left,level+1)    
        if node.right:pre_order(node.right,level+1)  
        return ans 

    def in_order(node,level):
        if len(ans)==level:
            ans.append([])
        if node.left: in_order(node.left,level+1)
        ans[level].append(node.val) 
        if node.right: in_order(node.right,level+1)
        return ans

    def post_order(node,level):
        if len(ans)==level:
            ans.append([])
        if node.left: post_order(node.left,level+1)
        if node.right: post_order(node.right,level+1)
        ans[level].append(node.val)
        return ans

    #-----------------------#
    #--select DFS approach--#
    #-----------------------#
    #1 preorder
    return pre_order(self.root,level)
    
    #2 inorder
    #return in_order(self.root,level)
    
    #3 postorder
    #return post_order(self.root,level)

After solving BFS, I really want to solve it as follows.

DFS_badcode.py

    def DFS(self):
        q = [self.root]
        ans = []
        level = 0
        def preorder(q,level):
            if len(ans)==level:
                ans.append([])
            nums = q.pop(0)
            ans[level].append(nums.val)
            if nums.left:
               q.append(nums.left)
               preorder(q,level+1)
            if nums.right:
               q.append(nums.right)
               preorder(q,level+1)
            return ans
        return preorder(q,level)

This code once starts with a "buffer" like the one I imagined in BFS. This is a result that could not be considered separately. DFS will search the entire tree without permission even if you think about the data alone. It's okay to throw away the image of the buffer and use it, which was a good learning experience.

Exercise 3 Maximum Depth of Binary Tree

`Find the maximum depth of a given Tree. ``

Answer_Image.py

Input: root = [4,2,6,1,3,5]
Output:3      #-----Tree_image---#
              #         4        #
              #      /     \     #
              #     2       6    #
              #    / \     /     #
              #   1   3   5      #
              #------------------#

[Restrictions] ・ Tree elements consist of 0 ~ 10 ^ 4 ・ -100 <= node.val <= 100

Commentary

The answers of the experts were as follows.

answer.py

    def maxDepth(self, root: TreeNode) -> int:    
        if not root:
            return 0
        else:
            left = self.maxDepth(root.left)+1
            right = self.maxDepth(root.right)+1
            return max(left,right)
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

leatcode passes above, but When I try various things locally, I change it a little as follows.

answer.py

    def maxDepth(self):
        def helper(node):   
            if not root:
               return 0
            else:
               left = helper(root.left)+1
               right = helper(root.right)+1
               return max(left,right)
        return max(helper(self.root.left),helper(self.root.right))+1

Point Even if you can't reach leaf with `leaf or none node, it counts all of them. Since what I want is the maximum value, there is no problem with the return approach of using max () to find the answer. Since the author's image and understanding have come together while dealing with other problems When I tried again, it was accepted with the following description.

maxDepth.py

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:return 0
        L = self.maxDepth(root.left) + 1
        R = self.maxDepth(root.right) + 1
        return max(L,R)

I'm sorry to understand the current situation, but by suppressing the points I was able to optimize the description. However, even if the description can be optimized, the processing time and memory occupied area From the point of view, there seems to be a long way to go. I'm excited (´ ▽ ｀) /

Exercise 4 Minimum Depth of Binary Tree

`Find the minimum depth of a given binary search tree. ``

Answer_sample.py

#Example 1
Input: root = [3,9,20,null,null,15,7]
Output: 2

#Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

[Restrictions] -The number of nodes that make up Tree is 0 ~ 10 ^ 5 -1000 <= node.val <= 1000

Commentary

I tried to find out what could be done by diverting the Maximum Depth of Binary Tree. By conditioning with if node.left or if node.right I expected None node to count and output only what I needed, without counting.

MinDepth.py

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        self.L,self.R = 0,0
        def helper(node):
            if not node:return 0
            else:
                if node.left: self.L = helper(node.left)+1
                if node.right:self.R = helper(node.right)+1
                return min(self.L,self.R)
        return helper(root) +1

The Run code passed, but the submit did not. That's right. This code has a major drawback. First, take a look at the tree structure below.

Tree_image.py

   0
    \
     1
      \
       2

As you can see, self.L has no value updates. After updating self.R, if you finally set it to min (self.L, self.R) The initial value of 0 in self.L is smaller, so the output is 0 + 1. I really want 3. .. Sorry.

POINT1 `If ​​you include return 0 in a recursive loop It is possible that 0 will be returned outside the deepest part of the tree, resulting in a minimum value. Therefore, in the case of a problem that counts the minimum value, only the counted value is always returned. ``

POINT2 `The approach of separating the left subtree and the right subtree and finally using min () to find the answer is The problem of finding this minimum is strictly prohibited. Items that are cut off in the middle can be adopted as the minimum value, As mentioned above, if there are no elements at all, the initial value will be returned, which is a bad idea. ``

In the first place, it is good if the initial value is not set to 0, If you write it incorrectly, the search result will be added to the set initial value. For example, let M be infinite as a reference, I think it is better to always compare and update the smaller one compared to M. ``

minDepth.py

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:return 0
        if not root.left and not root.right:return 1
        #self.M = float("inf") #<=You can put M here
        def helper(node,cnt):
            M = float("inf")
            if not node.left and not node.right:return cnt
            if node.left: M = min(M,helper(node.left,cnt+1))
            if node.right:M = min(M,helper(node.right,cnt+1))
            return M
        return helper(root,1)

Just in case, use GiF to check the image.

Exercise 5 Symmetric Tree

`Check if the tree is the target. ``

answer_image.py

#For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

     1
    / \
   2   2
  / \ / \
 3  4 4  3
# => return True 

#But the following [1,2,2,null,3,null,3] is not:

     1
    / \
   2   2
    \   \
    3    3
#=> return False

Commentary

If the movement of DFS so far is based on the image I think there is a policy to compare and confirm the symmetrical elements each time. The problem is how to achieve it. After all, I didn't understand and referred to the opinions of experts. It was so sophisticated that I made my eyes round.

SymetricTree.py

def Symetric(root):
    if not root:return True
    def helper(t1,t2):
        if not t1 and not t2:return True
        if not t1  or not t2:return False
        return (t1.val == t2.val) and helper(t1.left,t2.right) and helper(t1.right,t2.left)
    return helper(root.left,root.right)

It is difficult to capture the whole picture from the above, so I will try to swallow it little by little by dividing it into cases. For example, if the given Tree is [], then True is returned because "none" is the target. This is true even if the Tree element is root only, that is, [0]. This is because both the left and right sides hanging from root are "none". In the figure below, the left side is [] and the right side is [0]. Next, let's read the program by taking the following asymmetric case as an example. You can see that if t1 and t2 are asymmetric, it returns False. Let's consider making the tree a little larger. If you tell the points in advance, the following description is a miso.

point.py

return (t1.val == t2.val) and helper(t1.left,t2.right) and helper(t1.right,t2.left)

In this description, t1.val == t2.val is used to compare elements on the same hierarchy. Besides that, there is a mysterious description such as helper (t1.left, t2.right) and helper (t1.right, t2.left). To explain in order, helper (t1.left, t2.right) confirms whether the left child associated with t1 and the right child associated with t2 are symmetrical. helper (t1.right, t2.left) checks whether the right child associated with t1 and the left child associated with t2 are symmetric. In other words, it is a recursive process that checks whether the elements hanging from t1 and t2 are the target. Check it out in the GIF below. If the child associated with t1 and t2 is further branched, until True or False is returned at the branch destination. It is a mechanism to descend to the lower layer. It may be a slapstick, but the environment created for verification is as follows.

Tree.py

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

def Symmetric(node):
    if not root:return True
    def helper(t1,t2):
        if not t1 and not t2:return True
        if not t1 or  not t2:return False
        return (t1.val == t2.val) and \
               (helper(t1.left,t2.right)) and\
               (helper(t2.left,t1.right))            
    return helper(node.left,node.right)

    ##Tree_image####
    #        0 
    #      /   \
    #     1     1
    #    / \   / \   
    #   2   3 3   2
    ################ 
root = node(0)
root.left = node(1)
root.right = node(1)
root.left.left = node(2)
root.left.right = node(3)
root.right.left = node(3)
root.right.right = node(2)
print(Symmetric(root))

Exercise 6 Path sum

`If ​​the sum between root <=> leaf matches sum in the given tree, Returns True, False if they do not match. ``

answer_image.py

#Example:
#Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1 

Commentary

While remembering the description of the partial sum that I studied I examined whether it applies to this problem.

PathSum_solution1.py

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:return False
        if not root.left and not root.right:
            return sum-root.val == 0
        if self.hasPathSum(root.left,sum-root.val):
            return True
        if self.hasPathSum(root.right,sum-root.val):
            return True
        return False

It is undeniable that the above description is an ambiguous understanding. I decided to make a GIF and chase after it. I tried to verify two cases of True with sum = 7. I was able to confirm the movement of DFS itself again. Even if there is an if minute, it doesn't seem to change. The following two points were interesting to follow the movement.

POINT 1. If you want to include recursive processing in the conditional statement of if, as at the beginning Incorporate not root as a conditional statement for if and make it Return False. This allows you to return none node as false before reaching leaf. If the conditional statement of if is false by this, the if part is passed and the next if part is moved to. This is the reason for DFS, as the next if will search for node.right.

POINT 2. If you get to leaf return sum-root.val == 0 returns True or False. If the if conditional statement is True, it will be return True, and If False, move to the next if minute. If that doesn't work, the total value will not meet the requirements even if you perform a full search with DFS. It is configured to return False.

But I found a better answer. Understand the author with a little effort I commented. I'm afraid to comment on great code. ..

PathSum_solution2.py

def PathSum(node,sum):
    #before reaching the leaf, if it face None node. it is false.
    if not node:return False
    #subtract node.val from sum every time, we go through the node.
    sum -= node.val
    # if we reach the leaf, let us check whether path sum equals sum. 
    if not node.left and not node.right: 
        return sum == 0
    #First time,we subtract node.val from sum
    #after that,let us use recursive approach to research the rest node. 
    return PathSum(node.left,sum) or PathSum(node.right,sum) 

I was allowed to study.

It's fun to know that you don't understand (laughs)