Data Structure Trees: Concepts and C++ Implementations

Data Structure Trees: Fundamentals

A tree is a non-linear data structure that represents data in a hierarchical form. It consists of nodes connected by edges.

Key Tree Terminology

• Root Node: The topmost node (has no parent).
• Parent Node: A node that has child nodes.
• Child Node: Nodes that have a parent.
• Leaf Node: Nodes with no children.
• Edge: The connection between two nodes.
• Level: Distance from the root (root = level 0).
• Height: The length of the longest path from the root to a leaf.

C++ Node Structure Example

This structure defines a basic node for a binary tree:

#include <iostream>
using namespace std;

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

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

Binary Tree vs. Binary Search Tree (BST)

Binary Tree

A tree where each node has at most two children, referred to as the left and right child.

Binary Search Tree (BST)

A binary tree with an added ordering property: for any given node, all nodes in its left subtree have values less than the node, and all nodes in its right subtree have values greater than the node. This ordering makes searching, adding, and deleting efficient.

Tree Traversals

Tree traversals are ways to visit each node exactly once in a specific order. There are two main categories: depth-first and breadth-first.

Depth-First Traversal (DFT)

Explores as far as possible along each branch before backtracking.

• Pre-order: Visit the root, then the left subtree, then the right subtree (Root → Left → Right).
• In-order: Visit the left subtree, then the root, then the right subtree (Left → Root → Right). For a BST, an in-order traversal yields the nodes in ascending order.
• Post-order: Visit the left subtree, then the right subtree, then the root (Left → Right → Root).

Breadth-First Traversal (BFT)

Explores the tree level by level, from top to bottom.

• Level-order: Visits all nodes at the current depth before moving on to the nodes at the next depth. This is also called Breadth-First Search (BFS).

Traversal C++ Implementations

Preorder Traversal

void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

Inorder Traversal

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

Postorder Traversal

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Level Order Traversal (BFS)

#include <queue>
void levelOrder(Node* root) {
    if (root == nullptr) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        cout << curr->data << " ";
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

Types of Binary Trees

• Full Binary Tree: A binary tree where every node has either 0 or 2 children.
• Complete Binary Tree: A binary tree where all levels are filled, except possibly the last level, which is filled from left to right.
• Balanced Binary Tree: A binary tree where the height difference between the left and right subtrees of every node is minimal. This helps ensure efficient search times, as seen in AVL trees.
• Skewed (or Degenerate) Tree: A tree that resembles a linked list, where nodes have only one child (either all left or all right children).

Sample Job Application (Irrelevant Content Removed for Focus)

The following section appears to be unrelated to the data structure topic and has been retained as per instructions, though formatted separately.

To,

The Manager,

ABC Company,

New Delhi.

Subject: Application for the post of Software Developer

Sir/Madam,

I am writing to apply for the post of Software Developer in your esteemed organization. I am a B.Tech student in Computer Science with strong skills in C++, Data Structures, and Web Development. I am eager to utilize my technical knowledge and problem-solving abilities to contribute to your company’s success.

I am a hardworking, quick learner and dedicated individual who is passionate about technology and innovation. I would be grateful if you consider my application and provide me the opportunity to prove my abilities.

Thanking you,

Yours faithfully,

(Signature)

Sudhanshu Bhardwaj

Address: [Your Address]

Email: [Your Email]

Phone: [Your Number]