Trees Pt I

Trees: All Branches One place

Trees are hierarchal data structures built to store information that is connected to each other. As the name suggests, it is a tree, just upside down that stores data in its leaves and connected through branches. 

So, this was the introduction, now let's see what we gonna cover in this blog:

1. Applications of trees
2. Binary Trees
3. Traversals
4. Some Trivial Questions
5. The diameter of a binary tree
6. LCA of Binary Tree
7. Questions(Trivial)

This is all we gonna cover. This part is not that much tough, but it's likely to get a little frustrating when it comes to trivial questions. (At least for me 😢 )

Applications of Trees

So, why it is in this game anyway? Besides making really tough questions, trees are used to store information that is hierarchal in nature. And the world is flooded with such information, the organizational data, and you got the point. But what's the use in programming specifically?

Ever seen JSON/XML/HTML? Let's talk about HTML. HTML is a programming language(Is it though?😒) that stores all the divs, spans, and other elements in the form of a tree. The folder structure, where you keep 100 GBs of Study Material(I know it.😉) are tree data structures. Though very simple to understand, you can see they are used in various things. 

So, let's start learning them!

Tree Terminology and Structure in Memory:

Node: It's a structure we gonna use(in implementation) but for now, it refers to an element. It would contain 2 pointers and a data field. The pointers would contain the address to the next nodes(left and right node). See image

So, we build a structure in C++ like this:

struct Node{
    int data;
    Node *left,*right;
    Nod(int k)
    {
        data=k;
        left=right=NULL;
    }
}

Now we can use this structure to create a node. Note that this might be one way to store the tree, we have other ways as well, but to store a binary tree, this is by far the most easiest and accepted one. 

Also, when we would read graphs, we could see that all trees are graphs, and the problems we generally encounter as Codeforces D or E are mostly solved by treating the tree as a graph(though it depends on the question but in most cases, we would not be using this implementation except in segment trees.)

Trees Types

So, it's kinda weird but true that we would be jumping straight to Binary trees and all their traversals, and properties but not to any general tree. Not that a general tree is tough to understand, but the thing is that we can't have many generalized properties on all of them. Also, Binary trees are the most widely used tree data structures. they are used in segment trees, BST, Binary heap. So, we just restrict ourselves to binary trees. But we get a ton of things from binary trees only. So let's jump to Binary trees:

Binary Trees

Those trees which have at most 2 children on a node are known as Binary trees. 

We would be seeing its traversals, and variations.

Traversals

So, we have our tree, but now we want to have a ride on it, search for something, and for that, we need some algorithms for traversals.

So for traversal, we have these things: We are on the root node, and our left pointer would contain ride to the left node and similarly for the right node, but the order differs them all. So we have 3! permutations of choosing a traversal. But for some reason(I don't know it yet), we choose only three permutations.  

And we got them here:

• BFS
• DFS
• Inorder Traversal(Left->Root->Right)
• Preorder Traversal(Root->Left->Right)
• Postorder traversal(Left->Right->Root)

Now there is something I gotta tell: We always go from left to right in any kind of DFS traversals.

So, let's construct a tree and have a traversal of tree:

#include<iostream>
using namespace std;
void aeh()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
struct Node
{
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
}
void postOrder(struct Node *node)
{
    //postOrder=Left->Right->Root
    postOrder(node->Left);
    postOrder(node->Right);
    cout << node->data << " ";
}
void inOrder(struct Node *node)
{

    //inOrder=Left->Root->Right
    inOrder(node->Left);
    cout << node->data << " ";
    inOrder(node->Right);
}
void preOrder(struct Node *node)
{

    //preOrder=Root->Left->Right
    cout << node->data << " ";
    preOrder(node->Left);
    preOrder(node->Right);
}

int main()
{
    aeh();
    struct Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "\nPreorder traversal of binary tree is \n"; 
    printPreorder(root); 
  
    cout << "\nInorder traversal of binary tree is \n"; 
    printInorder(root);  
  
    cout << "\nPostorder traversal of binary tree is \n"; 
    printPostorder(root); 
    
    return 0;
}

Simple Enough