C++ Coding Test Course, Finding the Parent of a Tree

Problem Description

Write a program to find the parent node of each node in a given binary tree. The nodes of the binary tree are labeled with numbers and are defined with the following structure:

    struct Node {
        int value;
        Node* left;
        Node* right;
        
        Node(int val) : value(val), left(nullptr), right(nullptr) {}
    };
    

You will be given a list of nodes as input and the value of the requested node. The output should be the value of the parent node of the specified node, and if there is no parent node, it should return -1.

Example

    Input:
    5
    2 1
    7 3
    6 4
    0 -1
    Requested Node: 3
    
    Output:
    7
    

Approach to the Problem

To solve the problem, we will traverse the binary tree to identify the parent of each node. We will follow these steps:

1. Set the root node of the tree as the starting point.
2. Use a queue to explore the nodes of the tree in a BFS (Breadth-First Search) manner.
3. Check each node and store the parent of the requested node.
4. Once the requested node is found, print the corresponding parent node.

Code Implementation

    #include 
    #include 
    #include 
    using namespace std;

    struct Node {
        int value;
        Node* left;
        Node* right;

        Node(int val) : value(val), left(nullptr), right(nullptr) {}
    };

    Node* buildTree(const vector>& nodes) {
        unordered_map nodeMap;
        for (const auto& p : nodes) {
            int child = p.first;
            int parent = p.second;

            if (nodeMap.find(child) == nodeMap.end())
                nodeMap[child] = new Node(child);

            if (parent != -1) {
                if (nodeMap.find(parent) == nodeMap.end())
                    nodeMap[parent] = new Node(parent);

                if (!nodeMap[parent]->left)
                    nodeMap[parent]->left = nodeMap[child];
                else
                    nodeMap[parent]->right = nodeMap[child];
            }
        }
        return nodeMap.begin()->second; // Return the first added node as root
    }

    int findParent(Node* root, int target) {
        if (!root) return -1;

        queue q;
        q.push(root);
        Node* parent = nullptr;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Node* current = q.front();
                q.pop();
                
                if (current->left) {
                    if (current->left->value == target) {
                        return current->value;
                    }
                    q.push(current->left);
                }

                if (current->right) {
                    if (current->right->value == target) {
                        return current->value;
                    }
                    q.push(current->right);
                }
            }
        }
        
        return -1; // If parent is not found
    }

    int main() {
        // Tree structure: (child, parent)
        vector> nodes = {{2, 1}, {7, 3}, {6, 4}, {5, -1}};

        Node* root = buildTree(nodes); // Build tree
        int target = 3; // Requested node
        int parentValue = findParent(root, target);

        cout << parentValue << endl; // Print parent

        return 0;
    }
    

Code Explanation

The code above illustrates the overall process of constructing a binary tree and finding the parent of the requested node.

• buildTree: This function constructs the tree using the provided (child, parent) list. It stores each node in a map to establish the parent-child relationship.
• findParent: This function uses BFS to find the parent of the requested value. It traverses each node and returns the value of the current node if the child node equals the requested value.
• main: The entry point of the program, which builds the tree using sample input and finds the parent.

Conclusion

This problem is beneficial for understanding the basic structure of a binary tree and learning how to effectively utilize data structures. The process of exploring nodes and finding parent nodes through BFS is a widely used approach in real-world applications. Care should be taken at each step, and addressing exceptions can help prevent issues.

Additional Problems

As a variation of this problem, consider finding the child nodes of a specific node or calculating the depth of the tree. Various variation problems can deepen your understanding of trees.

Tips and Cautions

• When using recursion, be careful not to fall into an infinite loop.
• Clearly define conditions to handle cases where a node has no parent.
• The performance of the algorithm may vary based on the structure of the tree, so experiment with various cases.