Tree #1 Count Number of SubTrees having given Sum

Writer: Steven, Lee

Date: 4/10, Wednesday

Purpose: Count Number of SubTrees having given Sum

Topic:  Tree, Recursion

Level: Medium

Percentage: 57.88% have solved this problem

Time: it took me 30 minutes :)

Time Complexity: O(n) worst case

Runtime: 13 ms

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself

* Description *

 Given a binary tree containing N+1 with N edges nodes and an integer X. Your task is to complete the function countSubtreesWithSumX() that returns the count of the number of subtress having total node’s data sum equal to a value X.

Input:
 First line of input contains number of testcases T. For each testcase, first line of input contains number of edges in the tree. Next line contains information as X Y L or X Y R which means Y is on the left of X or Y is on the right of X respectively. Last line contains sum.

Output:
 For each test case count the number of subtrees with given sum.

Constraints:
1 <= T <= 103
1 <= N <= 103
-103 <= Node Value <= 103

* Example *

 #1 Ex)  

For the tree given below:            

              5
            /    \
        -10     3
        /    \    /  \
      9     8  -4 7

Subtree with sum 7:
             -10
            /      \
          9        8

and one node 7.

#2 Ex)  $  You need to print out this format  $

Input:
2
6
5 -10 L 5 3 R -10 9 L -10 8 R 3 -4 L 3 7 R
7
2
1 2 L 1 3 R
5

Output:
2
0

Explanation:
 Testcase 1: Subtrees with sum 7 are [9, 8, -10] and [7].

Note:

 Please note that it's Function problem i.e. you need to write your solution in the form of Function(s) only. Driver Code to call/invoke your function is already defined

* IDEA (Concept) *

 if you are familiar with the traversal, it gonna be a piece of cake. Normally, there are three algorithms PreOrder,  InOrder, PastOrder. 

PreOrder is defined as follows. (Root -> Left -> Right)

1. Visit the root

2. Traverse the left subtree

3. Traverse the right subtree

InOrder traversal is defined as follows. (Left -> Root -> Right)

1. Traverse the left subtree 

2. Visit the root 

3. Traverse the right subtree.

 

PostOrder is defined as follows. (Left -> Right -> Root)

1. Traverse the left subtree

2. Traverse the right subtree

3. Visit the root.

Let me give u some examples of this.  

Here is the example

              1

            /    \

         2       3

        /    \    /   \

      4     5  6   7 

   \

    8

PreOrder:  1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 8 -> 7

InOrder:    4 -> 2 -> 5 -> 1 -> 6 -> 8 -> 3 -> 7

PostOrder: 4 -> 5 -> 2 -> 8 -> 6 -> 7 -> 3 -> 1

* IDEA (Problem) *

 I've solved it with Post-Order traverse. Actually, I found that this approach could exactly bring in root and child nodes when it is on the root. Because this order is left -> right -> root . After we got nodes, we just check whether the sum of values in nodes is equal to the target or not. Here are some rules. If you are on the root node, then replace the value with the sum on the root and make the left child and the right child of the root null (we don't need to traverse here again ) if it's only equal, then we need to increase a count. Let me give u an example

Here is the example

   * Given tree *            * Target *                    * Count * 

              5                                  7                                        0
            /    \
        -10     3                              
        /    \    /  \
      9     8  -4 7

=> You are on 9 it's not equal to the target 

* count == 0 *   

* sum == 9 *

              5                                 
            /    \
        -10     3                              
        /    \    /  \
      9     8  -4  7

=> You are on 8 it's not equal to the target  

* count == 0 *

* sum == 8 *

              5                                 
            /    \
        -10     3                              
        /    \    /  \
      9     8  -4  7

=> You are on -10 It's equal to the target  

* count == 1 *    * the node representing 9 should be null *

* sum == 7 *      * the node representing 8 should be null *

              5                                 
            /    \
          7      3                              
        /    \    /  \
      n     n  -4  7

=> You are on -4 it's not equal to the target

* count == 1 *   

* sum == -4 *      

              5                                 
            /    \
          7      3                              
        /    \    /  \
      n     n  -4  7

=> You are on 7 it's equal to the target

* count == 2 *   

* sum == 7 *      

              5                                 
            /    \
          7      3                              
        /    \    /  \
      n     n  -4  7

=> You are on 3 it's not equal to the target

* count == 2 *    * the node representing -4 should be null *

* sum == 6 *      * the node representing 7 should be null *

              5                                 
            /    \
          7      6                              
        /    \    /  \
      n     n  n  n

=> You are on 5 it's not equal to the target

* count == 2 *      * the node representing 7 should be null *

* sum == 18 *      * the node representing 6 should be null *

              5                                 
            /    \
          n      n                              
        /    \    /  \
      n     n  n  n

 

I wish you understand it :) Thank u

(한국어)

 

* 난이도: 중간 *

* 오직 57.88%만이 이 문제를 풀었습니다. *

* 트리와 순회가 핵심 부분입니다. *

* 저는 30분 정도가 걸렸습니다. *

* 시간 복잡도는 O(n)입니다 *

* 런타임은 13ms입니다. *

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

 N+1와 N을 포함한 이진트리와 정수 X가 주어진다. 이때 하위트리의 모든 값의 합이 정수 X와 같은 트리가 몇개인지 반환하는 함수 countSubtreesWithSumX()를 작성하시오.

입력:

 인풋의 첫 번째 줄에는 테스트 수인 T가 들어온다. 각 테스트의 첫 번째 줄은 트리의 간선의 수를 나타낸다. 다음 줄에는 Y가 X의 왼쪽에 있거나 Y가 X의 오른쪽에 있다는 것을 의미하는 X Y L 또는 X Y R가 들어온다.

출력:

  각 시험 사례에 대해 주어진 합계와 동일한 값을 가진 하위 트리의 수를 카운트해서 출력하시오.

제한:
1 <= T <= 103
1 <= N <= 103
-103 <= Node Value <= 103

* 예시 *

 #1 Ex)  

주어진 트리는 아래와 같다:            

              5
            /    \
        -10     3
        /    \    /  \
      9     8  -4 7

합계가 7인 하위 트리:
             -10
            /      \
          9        8

하나의 노드인 7.

#2 Ex)  $  이와 같은 형식으로 출력해야 합니다.  $

입력:
2
6
5 -10 L 5 3 R -10 9 L -10 8 R 3 -4 L 3 7 R
7
2
1 2 L 1 3 R
5

출력:
2
0

설명:

 테스트 1: 합계가 7인 하위트리는 [9, 8, -10] 그리고 [7]이다.

Note:

 이 문제는 함수 문제입니다. 즉, 함수에서 솔루션만 작성하시면 됩니다. 여러분의 함수를 부르는 Driver code는 이미 정의되어 있습니다. ( 입력과 출력을 신경 쓸 필요가 없습니다. )

* 아이디어 (개념) *

 만약 여러분들이 순회라는 개념과 친숙하다면 이 문제는 꽤 쉬울 것 같습니다. 순회에서는 총 3가지 알고리즘이 있습니다. 전위순회, 중위순회, 후위순회입니다.

전위 순회는 다음과 같이 정의됩니다. ( 루트 -> 왼쪽 -> 오른쪽)

   1. 루트를 방문합니다.

   2. 왼쪽 하위트리에 순회합니다.

   3. 오른쪽 하위트리에 순회합니다. 

 중위 순회는 다음과 같이 정의됩니다. ( 왼쪽 -> 루트 -> 오른쪽)

1. 왼쪽 하위트리를 순회합니다.

2. 루트를 방문합니다.

3. 오른쪽 하위트리를 순회합니다.

  후위 순회는 다음과 같이 정의됩니다. ( 왼쪽 -> 오른쪽 -> 루트)

 1. 왼쪽 하위트리를 순회합니다.

 2. 오른쪽 하위트리를 순회합니다.

 3. 루트를 방문합니다.

예시입니다.

              1

            /    \

         2       3

        /    \    /   \

      4     5  6   7 

   \

    8

전위 순회:  1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 8 -> 7

중위 순회:  4 -> 2 -> 5 -> 1 -> 6 -> 8 -> 3 -> 7

후위 순회:  4 -> 5 -> 2 -> 8 -> 6 -> 7 -> 3 -> 1

* IDEA (Problem) *

 저는 이 문제를 후위 순회로 풀었습니다. 이 순회는 루트에 있을 때 자식 노드와 루트 노드를 한번에 가져 올 수 있다는 사실을 알았습니다. 왜냐하면 이 순서가 왼쪽 -> 오른쪽 -> 루트이기 떄문입니다. 노드들은 가진 후에 그 노드에 있는 값들의 합이 대상과 같은지 확인하면 됩니다. 규칙들이 몇 개 있습니다. 만약 루트에 있다면 그 합계를 루트의 값과 교체를 합니다. 그리고 그 루트의 왼쪽 자식과 오른쪽 자식을 null로 만듭니다 ( 여기에 다시 방문할 필요가 없기 때문임 ). 만약 같다면 카운트를 증가하면 됩니다. 

 예시입니다.

       * 트리 *                 * Target *                     * Count * 

              5                                  7                                        0
            /    \
        -10     3                              
        /    \    /  \
      9     8  -4 7

=> 9에 있고 합이 대상과 같지 않습니다.

* count == 0 *   

* sum == 9 *

              5                                 
            /    \
        -10     3                              
        /    \    /  \
      9     8  -4  7

=> 8에 있고 합이 대상과 같지 않습니다.

* count == 0 *

* sum == 8 *

              5                                 
            /    \
        -10     3                              
        /    \    /  \
      9     8  -4  7

=>  -10에 있고 합이 대상과 같습니다.

* count == 1 *    * 9를 가지고 있는 노드를 null로 바꿉니다. *

* sum == 7 *      * 8를 가지고 있는 노드를 null로 바꿉니다. *

              5                                 
            /    \
          7      3                              
        /    \    /  \
      n     n  -4  7

=> -4에 있고 합이 대상과 같지 않습니다.

* count == 1 *   

* sum == -4 *      

              5                                 
            /    \
          7      3                              
        /    \    /  \
      n     n  -4  7

=> 7에 있고 합이 대상과 같습니다.

* count == 2 *   

* sum == 7 *      

              5                                 
            /    \
          7      3                              
        /    \    /  \
      n     n  -4  7

=> 3에 있고 합이 대상과 같지 않습니다.

* count == 2 *    * -4를 가지고 있는 노드를 null로 바꿉니다. *

* sum == 6 *      * 7를 가지고 있는 노드를 null로 바꿉니다. *

              5                                 
            /    \
          7      6                              
        /    \    /  \
      n     n  n  n

=> 5에 있고 합이 대상과 같지 않습니다.

* count == 2 *    * 7를 가지고 있는 노드를 null로 바꿉니다. *

* sum == 18 *    * 6를 가지고 있는 노드를 null로 바꿉니다. *

              5                                 
            /    \
          n      n                              
        /    \    /  \
      n     n  n  n

 

감사합니다 ^_^/

* Check *

You can check it out here

이 사이트에서 정답의 유무를 확인하실 수 있습니다.

https://practice.geeksforgeeks.org/problems/count-number-of-subtrees-having-given-sum/1

 
import java.util.*;
 
 
class Node{
    int data;
    Node left,right;
    Node(int d) {data = d; left =right= null; }
}
    
public class CountNumberOfSubTreesHavingGivenSum {
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
 
        while(t-->0){
            int n = sc.nextInt();
            Node root=null, parent=null;
            HashMap<Integer, Node> m = new HashMap<>();
            
            for(int i=0;i<n;i++){
                int a=sc.nextInt();
                int b=sc.nextInt();
                char c=sc.next().charAt(0);
                if(m.containsKey(a)==false){
                    parent=new Node(a);
                    m.put(a,parent);
                    if(root==null)
                        root=parent;
                }
                else
                    parent=m.get(a);
                Node child=new Node(b);
                if(c=='L')
                    parent.left=child;
                else
                    parent.right=child;
                m.put(b,child);
            }
            
            int x=sc.nextInt();
            Solution obj = new Solution();
            System.out.println(obj.countSubtreesWithSumX(root, x));
        }
    }
}
 
class Solution{
    public static int count = 0;
    
    public Solution() {
        count = 0;
    }
    
    public int countSubtreesWithSumX(Node root, int x){
        if(root == null) { return count; }
   
        countSubtreesWithSumX(root.left, x);
        countSubtreesWithSumX(root.right, x);
        
        int sum;
          if(root.left != null && root.right == null)
            sum = root.left.data + root.data;
          else if(root.left == null && root.right != null) 
            sum = root.right.data + root.data;
        else if(root.left != null && root.right != null)
            sum = root.left.data + root.right.data + root.data;
        else
            sum = root.data;
          
        
        if(sum == x) count+=1;
        
        root.data = sum;
        root.left = null;
        root.right = null;
 
        
        return count;
    }
}