Converting Org Tree to Engineer-Only Graph

🌳 Problem Statement

You are given a tree representing a company's organizational structure. The root is always an Engineer.

Each node (Employee) has:

• id (Integer)
• isEngineer (Boolean)
• reportees (List of Employees)

The Task: Convert this graph into a new graph that contains only Engineers.

• The hierarchy must be preserved as much as possible.
• If an Engineer reports to a Non-Engineer, they should "move up" to report to the nearest Engineer ancestor.
• Constraint: You should create a New Graph (Deep Copy), leaving the original structure untouched.

📝 Example Scenarios

Scenario 1: The "Bridge" Case (Non-Engineer Middleman)

A Non-Engineer sits between two Engineers. The bottom Engineer must move up.

Input Tree: Engineer(1) -> NonEngineer(2) -> Engineer(3)

Output Tree: Engineer(1) -> Engineer(3)

• Logic: NonEngineer(2) is removed. Engineer(3) is promoted to report directly to Engineer(1).

---

Scenario 2: The "Split" Case (Multiple Orphans)

A Non-Engineer has multiple Engineer reports. All of them must move up together.

Input Tree: Eng(1) -> NonEng(2) -> [Eng(3), Eng(4)]

Output Tree: Eng(1) -> [Eng(3), Eng(4)]

• Logic: When NonEng(2) is removed, both Eng(3) and Eng(4) become direct children of Eng(1).

---

1. The Core Logic: Recursive Filtering

This problem requires a Post-Order Traversal (Bottom-Up) approach. We must process the children before we can decide what the current node looks like.

📉 The Return Type Nuance

Standard tree traversals return a single Node. However, because a Non-Engineer "dissolves" and might leave behind multiple children, our recursive function must return a List of Nodes (or vector<Employee*>).

🧠 The Decision Matrix

For every node current:

1. Recurse: First, call the function on all children to get their "sanitized" lists of engineers. Flatten these results into a single list of valid_children.

2. Evaluate Self:

   • If current is Engineer:

     • Create a new copy of current.
     • Attach valid_children to this new node.

     • Return list [new_current].

       • If current is Non-Engineer:

     • Do not create a node.

     • Dissolve self and pass valid_children up to the parent.
     • Return valid_children (the list of orphans).

---

2. Example Walkthrough

Let's trace the logic using the specific example provided.

🖼️ Visual Example

Input Tree:

                        E1
        ________________|________________
        |               |               |
       E2              NE1             E3
    ___|___             |
    |     |             |
    E4    NE2           E5

Output Tree (Engineer Only):

                        E1
        ________________|________________
        |               |               |
       E2              E5               E3
       |
       E4

📊 Trace Table

Node	Type	Step 1: Process Children	Step 2: Decision	Return Value
E4	Eng	Leaf (No children)	Create New E4.	[New_E4]
NE2	Non-Eng	Leaf (No children)	Dissolve. Return empty list.	[]
E2	Eng	Receives [New_E4], [].	Create New E2. Attach [New_E4].	[New_E2]
E5	Eng	Leaf (No children)	Create New E5.	[New_E5]
NE1	Non-Eng	Receives [New_E5].	Dissolve. Pass [New_E5] up.	[New_E5]
E3	Eng	Leaf (No children)	Create New E3.	[New_E3]
E1	Eng	Receives: [New_E2], [New_E5], [New_E3]	Create New E1. Attach all 3 lists.	[New_E1]

🏁 Final Structure

New_E1 now has children: [New_E2, New_E5, New_E3]. New_E2 has child [New_E4].

---

3. Extension: In-Place vs. Deep Copy

Deep Copy (Selected Approach)

• Pros: Thread-safe, cleaner (functional style), original data remains valid for other uses (e.g., HR payroll needs Non-Engineers).
• Cons: \(O(N)\) extra space.

In-Place Modification

• Logic: Pointer manipulation. If child is Non-Engineer, move child->reportees into current->reportees, then delete child.
• Pros: \(O(1)\) extra space (excluding stack).
• Cons: Destructive. Complex iterator invalidation issues in C++ (modifying a vector while iterating it).

---

4. Practice & Edge Cases

🧪 Common Scenarios

1. The "Deep" Non-Engineer Chain
   • Scenario: E1 -> NE1 -> NE2 -> NE3 -> E5
   • Logic: The recursion bubbles E5 up through all layers. NE3 returns [E5], NE2 returns [E5], NE1 returns [E5]. Finally E1 adopts E5.
2. The "Leaf" Non-Engineer
   • Scenario: E1 -> NE1 (where NE1 has no children).
   • Logic: NE1 returns an empty list []. E1 adopts nothing. Result: E1 with no children.
3. Null Root
   • Logic: Return nullptr immediately.

---

🛠️ Interview Toolkit: Key Checks

Here is a cheat-sheet for "Strong Hire" signals during the interview.

1. Memory Ownership: Since we are using C++ new, explicitly mention who owns these pointers. (Ideally, use unique_ptr in production, but raw pointers are acceptable for whiteboard speed if acknowledged).
2. Complexity:
   • Time: \(O(N)\) (We visit every node once).
   • Space: \(O(N)\) (Recursion stack + New nodes).
3. Return Type Justification: Be ready to explain why you return a vector and not a single Employee*. (Answer: "Because a single node removal can result in multiple sub-trees needing re-parenting.")

---

💻 Appendix: Solution Code

C++ Solution (Deep Copy)

Click to expand solution code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Employee {
    int id;
    bool isEngineer;
    vector<Employee*> reportees;

    Employee(int id, bool isEngineer) : id(id), isEngineer(isEngineer) {}
};

class OrgChartConverter {
public:
    // Main API
    Employee* convertToEngineerGraph(Employee* root) {
        if (!root) return nullptr;

        // The root is guaranteed to be an Engineer, so result[0] is safe
        vector<Employee*> result = helper(root);
        return result.empty() ? nullptr : result[0];
    }

private:
    // Helper function: Returns a LIST of nodes because of the "dissolve" logic
    vector<Employee*> helper(Employee* current) {
        vector<Employee*> engineersList;
        if (!current) return engineersList;

        // 1. Recursively process all children first (Bottom-Up)
        vector<Employee*> processedSubtree;
        for (Employee* child : current->reportees) {
            vector<Employee*> childEngineers = helper(child);
            // Collect all valid engineers returned from the subtree
            processedSubtree.insert(processedSubtree.end(),
                                    childEngineers.begin(),
                                    childEngineers.end());
        }

        // 2. Process current node
        if (current->isEngineer) {
            // SCENARIO: Engineer -> Keep
            // Create a NEW node (Deep Copy)
            Employee* newEngNode = new Employee(current->id, true);

            // Adopt the collected subtree
            newEngNode->reportees = processedSubtree;

            // Return this node as the single result
            engineersList.push_back(newEngNode);
        } else {
            // SCENARIO: Non-Engineer -> Dissolve
            // Do NOT create a node.
            // Pass the processed children upwards to the parent
            engineersList = processedSubtree;
        }

        return engineersList;
    }
};