Senior2019-Set 4 - Recursive Functions and CNS 4

1. E

2. A

3. B

2. E

3. A

12. B

a = input() 
 
class Node(): 
    def __init__(self, value, depth=0): 
        self.value = value 
        self.left = self.right = None 
        self.depth = depth 
    def insert(self, value): 
        if value <= self.value: 
            if self.left == None: 
                self.left = Node(value, self.depth+1) 
                # print(f'{value} is the left child of {self.value}') 
            else: 
                self.left.insert(value) 
        if value > self.value: 
            if self.right == None: 
                self.right = Node(value, self.depth+1) 
                # print(f'{value} is the right child of {self.value}') 
            else: 
                self.right.insert(value) 
    def children(self): 
        children = 0 
        if self.left != None: children += 1 
        if self.right != None: children += 1 
        return children 
    def match(self, other): 
        if self.left == None and self.right == None: 
            return True 
        if other.left == None and self.left != None: 
            return False 
        if other.right == None and self.right != None: 
            return False 
        if self.left == None: 
            return self.right.match(other.right) 
        if self.right == None: 
            return self.left.match(other.left) 
        return self.left.match(other.left) and self.right.match(other.right) 
    def traverse(self): 
        # print(self.value, self.left, self.right) 
        yield self 
        if self.left != None: 
            yield from self.left.traverse() 
        if self.right != None: 
            yield from self.right.traverse() 
 
A = Node(a[0]) 
for c in a[1:]: 
    A.insert(c) 
 
leaf = external = external_path = internal_path = depth = 0 
for node in A.traverse(): 
    if node.children() == 0: 
        leaf += 1 
        external += 2 
        external_path += 2*(node.depth+1) 
    if node.children() == 1: 
        external += 1 
        external_path += node.depth+1 
    internal_path += node.depth 
    depth = max(node.depth, depth) 
 
print(depth, leaf, external, internal_path, external_path)

2. E

3. A

12. B

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ii pair<int, int>

#define vi vector<int>

#define vii vector<ii>

#define vs vector<string>

#define ll long long

#define ull usigned ll

#define INF 1000000000

int depth = 0;

int leaf = 0;

int ext = 0;

int intPath = 0;

int extPath = 0;

struct node{

int depth;

bool c1, c2;

char val = '~';

};

vector<node> nTree;

void insert(int depth, int pos, char t) {

if (nTree[pos].val == '~') {

nTree[pos].val = t;

nTree[pos].depth = depth;

} else {

if (t <= nTree[pos].val) {

nTree[pos].c1 = true;

insert(depth + 1, 2 * pos, t);

} else {

nTree[pos].c2 = true;

insert(depth + 1, 2 * pos + 1, t);

}

}

}

void dfs(int pos) {

if (!nTree[pos].c1 && !nTree[pos].c2) {

leaf++;

depth = max(depth, nTree[pos].depth);

ext += 2;

extPath += 2 * (nTree[pos].depth + 1);

intPath += nTree[pos].depth;

return;

}

intPath += nTree[pos].depth;

if (!nTree[pos].c1) {

extPath += nTree[pos].depth + 1;

ext++;

}

if (!nTree[pos].c2) {

extPath += nTree[pos].depth + 1;

ext++;

}

if (nTree[pos].c1) dfs(pos * 2);

if (nTree[pos].c2) dfs(pos * 2 + 1);

}

int main() {

string a;

cin >> a;

int maxSize = pow(2, a.size());

nTree.resize(maxSize + 1);

for (int i = 0; i < (int)a.size(); i++) {

insert(0, 1, a[i]);

}

dfs(1);

cout << depth << endl << leaf << endl << ext << endl << intPath << endl << extPath << endl;

}