CodeStepByStep

Write a recursive function named removeFile that deletes a directory or file from the file system represented as a binary tree as described below, including all descendent files/dirs inside it.

You can use a tree to represent a file system, with each node representing a directory or file. Since a directory can contain more than 2 files, a binary tree may seem like a poor choice. But you can do it using a structure where a node N's left child is the first child file inside N, and the right child is the next sibling file/dir within the same parent directory of N. (A normal file that isn't a directory will always have a null first child.) The following structure will work:

struct FileTreeNode {
    string name;                 // "data"  = file/directory name
    FileTreeNode* firstChild;    // "left"  = first child
    FileTreeNode* nextSibling;   // "right" = next sibling
};

For example, consider the set of directories and files shown below at left. The file system contains files such as "/bin/rm" and "/usr/lib/code/java". You can represent this set of files using the binary tree shown at right. Each "left" line shown below is the firstChild of the node above it; each right line shown below is the nextSibling of the node before it. The root of the overall file system is a FileTreeNode with an empty string as its name, the bin node as its firstChild, and a null nextSibling.

bin
    cat
    ls
    rm
    tar
home
    msahami
    stepp
    xuamyj
usr
    include
        h
    local
    lib
        apt
        code
            cpp
            java
            python
        dpkg
    share
    src
var

        ""
       /
    bin___________
   /              \
cat                home_____________________
  \               /                         \
   ls      msahami                           usr
     \            \                         /   \
      rm           stepp             include     var
        \               \           /       \
         tar             xuamyj    h         local
                                                  \
                                                   lib
                                                  /   \
                                               apt     share
                                                  \         \
                                                   code      src
                                                  /    \
                                               cpp      dpkg
                                                  \
                                                   java
                                                       \
                                                        python

For this problem, write a recursive function named removeFile that deletes a directory or file from the file system, including all descendent files/dirs inside it. Your function accepts two parameters: a reference to a FileTreeNode pointer for the root of the file system binary tree, and a string for the full path of the file or directory to delete, with / slashes between directories, such as "/usr/local/lib". Your function should remove the node of the tree that corresponds to that string's file path, along with all of its children, grandchildren, etc. If you remove a node, you should free its memory using delete. (You don't need to actually modify the computer's real file system, just the binary tree representing the file system.) If there is no node in the tree that corresponds to the string path passed in, your function should not modify the tree.

For example, if the file system tree above is represented by a FileTreeNode pointer named fs, and the call of removeFile(fs, "/usr/lib/code"); is made, you should modify the tree above to remove the nodes "code", "cpp", "java", and "python", making the next sibling after "apt" become "dpkg". If the string to remove were "/usr/lib" instead, a total of 7 nodes would be removed: "lib", "apt", "dpkg", plus the four from "/usr/lib/code" .

If the string passed is "" (the empty string), you should delete the entire file system (!!!).

Constraints: You must implement your function recursively and without using loops. Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc). Do not create any FileTreeNode objects. You may create pointers to objects, but not allocate 'new' objects. Do not leak memory. Your solution should be at worst O(N) time and must make only a single pass over the tree.