DILI #6

TREES(PART 1)

The trees I'm refering to are not those you see in the park with roots and leaves ... well these also have roots and leaves but it's not that kind of tree...You know what I mean. The trees I'm talking about are Binary Trees, Tertiary Trees and n-ary Trees. For example:

There are many applications for it, or that at least what the website said, like for sorting and searching or like how you see how the files in your folder or arrange with one file containing the others. For now, I have not learn that far but I know the basics. Like all the properties like how the maximum number of nodes there can be on a Binary Tree of height N is 2^N or in an n-ary Tree is n^N. But those are just things you can find on the Internet so here is the link to all of them.

Different from an array or a vector which are linear and can be access through indexing, a node on a tree can ony be access through other nodes or sequential and need to be "Traversed". There are generally 2 Tree Traversal algorithms:

• Depth-First Search (DFS) Algorithms, which can be further catergorised into 3 more:

1. Preorder Traversal (current-left-right)
2. Inorder Traversal (left-current-right)
3. Postorder Traversal (left-right-current)

• Breadth-First Search (BFS) Algorithms for now I can only find one which is Level Order Traversal(left-to-right, level-by-level)

Ultilizing the tree up there, these are examples for each Traversal that can help you get comfortable with them:

Pre-order Traversal of the above tree: 1-2-4-5-3-6-7
In-order Traversal of the above tree: 4-2-5-1-6-3-7
Post-order Traversal of the above tree: 4-5-2-6-7-3-1
Level-order Traversal of the above tree: 1-2-3-4-5-6-7

Now for the more technical part, how do you create a tree? There are no Tree data type so you can only manually create it via struct or class:

// Use any below method to implement Nodes of tree

// Method 1: Using "struct" to make
// user-define data type
struct node {
    int data;
    struct node* left;
    struct node* right;
};

// Method 2: Using "class" to make
// user-define data type
class Node {
public:
    int data;
    Node* left;
    Node* right;
};

But for actual programmes to be done, something more needs to be added. The NULL:

class Node {
public:
    int data;
    Node* left;
    Node* right;
    // Val is the key or the value that
    // has to be added to the data part
    Node(int val)
    {
        data = val;
        // Left and right child for node
        // will be initialized to null
        left = NULL;
        right = NULL;
    }
};

With the NULL, our Traversal Algorithms can know when to stop and check other branches of the Trees. For the 3s in DFS, all can be done using Recursion and only differs by the order of which we checked the current, left and right nodes so I'll let you figure out the other 2s and only do Preorder:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> nodes;
        preorder(root, nodes);
        return nodes;
    }
private:
    void preorder(TreeNode* root, vector<int>& nodes) {
        if (!root) {
            return;
        }
        nodes.push_back(root -> val);
        preorder(root -> left, nodes);
        preorder(root -> right, nodes);
    }
};

Just with a bit of shuffling you can get the other 2 quite simply. For BFS, it can be done iteratively but that introduces a new concept called "queue" so I will lay that off for now. I think that's enough for now. Anymore will be too much for you and me.

As always, any advices on coding or blog writing are much appreciated!

REFERENCE:
GeeksforGeeks
Alex's help with class 'cus I forgot to learn that