Sum of nodes inside Okay distance from goal

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

struct Node {

    int knowledge;

    Node* left;

    Node* proper;

    Node(int val)

    {

        this->knowledge = val;

        this->left = 0;

        this->proper = 0;

    }

};

  

void dfs(Node* root,

         unordered_map<Node*, Node*>& par)

{

    if (root == 0)

        return;

    if (root->left != 0)

        par[root->left] = root;

    if (root->proper != 0)

        par[root->right] = root;

    dfs(root->left, par);

    dfs(root->proper, par);

}

  

void dfs3(Node* root, int h, int& sum, int ok,

          unordered_map<Node*, int>& vis,

          unordered_map<Node*, Node*>& par)

{

    if (h == ok + 1)

        return;

    if (root == 0)

        return;

    if (vis[root])

        return;

    sum += root->knowledge;

    vis[root] = 1;

    dfs3(root->left, h + 1, sum, ok, vis, par);

    dfs3(root->proper, h + 1, sum, ok, vis, par);

    dfs3(par[root], h + 1, sum, ok, vis, par);

}

  

Node* dfs2(Node* root, int goal)

{

    if (root == 0)

        return 0;

    if (root->knowledge == goal)

        return root;

    Node* node1 = dfs2(root->left, goal);

    Node* node2 = dfs2(root->proper, goal);

    if (node1 != 0)

        return node1;

    if (node2 != 0)

        return node2;

}

  

int sum_at_distK(Node* root, int goal,

                 int ok)

{

    

    

    unordered_map<Node*, Node*> par;

  

    

    

    par[root] = 0;

  

    

    

    dfs(root, par);

  

    

    Node* node = dfs2(root, goal);

  

    

    

    unordered_map<Node*, int> vis;

  

    int sum = 0;

  

    

    dfs3(node, 0, sum, ok, vis, par);

    return sum;

}

  

int principal()

{

    

    Node* root = new Node(1);

    root->left = new Node(2);

    root->proper = new Node(9);

    root->left->left = new Node(4);

    root->right->left = new Node(5);

    root->right->proper = new Node(7);

    root->left->left->left = new Node(8);

    root->left->left->proper = new Node(19);

    root->right->right->left = new Node(20);

    root->right->right->proper

        = new Node(11);

    root->left->left->left->left

        = new Node(30);

    root->left->left->right->left

        = new Node(40);

    root->left->left->right->proper

        = new Node(50);

  

    int goal = 9, Okay = 1;

  

    

    cout << sum_at_distK(root, goal, Okay);

    return 0;

}