Introduction – What is Tree ?

Tree ek non-linear data structure hai jo hierarchical way me data ko store karta hai. Iska structure real life tree ki tarah hota hai, lekin opposite, root top pe hota hai aur branches neeche.

Tree ka use file systems, databases, parsing expressions, and searching algorithms me hota hai.

Basic Tree Terminologies

1. Root: Tree ka first node hota hai.
2. Node: Element ka har ek node.
3. Child: Kisi node ka connected down node.
4. Parent: Child node se connected upar wala node.
5. Leaf: Node jiska koi child nhi.
6. Subtree: Kisi node ke neeche ka pura tree structure.
7. Height: Root se leaf tak longest path

Advantages of Tree in DSA

1. Hierarchical Data Representation: Tree real-world jaise hierarchical data (like file explorer) ko easily represent karta hai.
2. Fast Searching & Sorting: Binary Search Tree (BST) me searching O(log n) time me ho sakti hai agar tree balanced ho.
3. Efficient Insertion/Deletion: Tree me insert aur delete operations efficient hote hain compared to arrays.
4. No Limit on Number of Nodes: Unlike arrays, tree me aap jitne chahe nodes add kar sakte ho, ye dynamic hota hai.
5. Traversal Flexibility: Tree me multiple tarike se traverse kiya ja sakta hai (Inorder, Preorder, Postorder, Level Order).

Disadvantages of Tree in DSA

1. Complex Implementation: Arrays aur Linked Lists ke comparison me Tree ka structure banana aur handle karna thoda complex hota hai.
2. Memory Usage: Har node ko pointer store karna padta hai (left & right), is wajah se extra memory use hoti hai.
3. Unbalanced Tree Issue: Agar tree unbalanced ho jaye (like skewed tree), to performance degrade ho jati hai (O(n)).
4. Difficult Debugging: Tree traversal ya recursion galat ho to bug find karna mushkil hota hai.

Applications of Trees:

1. File Systems: Windows/Linux ke file explorer tree structure par based hote hain.
2. Databases (Indexing): B-Trees aur AVL Trees ko database indexing me use kiye jate hai.
3. HTML DOM: Web browser ka DOM ek tree structure hota hai.
4. AI & Games: Decision trees, Minimax algorithm, etc.
5. Routing Algorithms: Network routing me spanning trees ka use hota hai.
6. Compilers: Expressions ko analyze karne ke liye syntax tree ya parse tree ka use hote.
7. Operating Systems: Directory management and process scheduling me use hota hai.

Implementation of Tree Structure C++

#include <iostream>
using namespace std;

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

    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

int main() {
    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 << "Root Node: " << root->data << endl;
    cout << "Left Child of Root: " << root->left->data << endl;
    cout << "Right Child of Root: " << root->right->data << endl;

    return 0;
}

Output:

Root Node: 1

Left Child of Root: 2

Right Child of Root: 3

Tree Structure

        1
       /  \
      2    3
     /      \
    4        5

Tree Traversal Techniques

Traversal ka matlab hota hai tree ke har node ko ek bar visit karna. Jaise array me hum left to right jaate hain, linked list me next pointer se aage badhte hain, waise hi tree me bhi ek systematic way hota hai nodes ko visit karne ka.

Tree ke 3 common depth-first traversal techniques hote hain:

1. Inorder: (Left, Root, Right)
2. Preorder: (Root, Left, Right)
3. Postorder: (Left, Right, Root)

1. Inorder Traversal (Left Root Right)

Explanation:

• Sabse pehle Left subtree visit karo
• Phir Current node (Root) print karo
• Last me Right subtree visit karo

Example Tree:

        1
       /  \
      2    3
     / \
    4   5

Inorder Traversal:

Output: 4 2 1 3 5

Code (Recursive in C++):

void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

 2. Preorder Traversal (Root Left Right)

Explanation:

• Sabse pehle Current node (Root) ko print karo
• Phir Left subtree visit karo
• Last me Right subtree

Same Tree:

        1
       / \
      2   3
     / \
    4   5

Preorder Traversal:

Output: 1 2 4 5 3

Code:

void preorder(Node* root) {
    if (root == NULL) return;

    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

3. Postorder Traversal (Left Right Root)

Explanation:

• Pehle Left subtree
• Phir Right subtree
• Last me Current node (Root)

Same Tree:

        1
       / \
      2   3
     / \
    4   5

Postorder Traversal:

Output: 4 5 2 3 1

Code:

void postorder(Node* root) {
    if (root == NULL) return;

    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Full Code in C++ for All Three Traversals

#include <iostream>
using namespace std;

// Node structure for Binary Tree
struct Node {
    int data;
    Node* left;
    Node* right;


    Node(int value) {
        data = value;
        left = right = NULL;
    }
};

// Inorder Traversal (Left, Root, Right)
void inorderTraversal(Node* root) {
    if (root == NULL) return;

    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

// Preorder Traversal (Root, Left, Right)
void preorderTraversal(Node* root) {
    if (root == NULL) return;

    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// Postorder Traversal (Left, Right, Root)
void postorderTraversal(Node* root) {
    if (root == NULL) return;

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << " ";
}

int main() {
    // Tree creation
    /*
            1
           / \
          2   3
         / \
        4   5
    */

    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);

    // Traversal outputs
    cout << "Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;

    cout << "Preorder Traversal: ";
    preorderTraversal(root);
    cout << endl;

    cout << "Postorder Traversal: ";
    postorderTraversal(root);
    cout << endl;

    return 0;
}

Output:

Inorder Traversal: 4 2 5 1 3  

Preorder Traversal: 1 2 4 5 3  

Postorder Traversal: 4 5 2 3 1