Trees: Introduction | DSA in C++ - Software Development PDF Download

Introduction

In the world of data structures, trees play a vital role in organizing and managing data efficiently. They provide a hierarchical structure that mimics a real-life tree with branches and leaves. In this article, we will explore the fundamentals of trees, their properties, and how to implement them in C++. We will cover basic tree terminologies, traversal techniques, and provide practical examples to solidify your understanding.

What is a Tree?

Basic Tree Terminologies

• Root: The topmost node of the tree, serving as the starting point.
• Node: The individual elements within a tree that holds data.
• Edge: The connection between two nodes.
• Parent: The node that is connected to one or more child nodes.
• Child: The node(s) connected to a parent node.
• Leaf: The nodes that do not have any child nodes.
• Subtree: A smaller tree formed by a node and its descendants.
• Height: The number of edges in the longest path from the root to a leaf node.
• Depth: The number of edges in the path from the root to a particular node.

Implementing Trees in C++

In C++, we can represent a tree using a struct or class. Here's an example of implementing a binary tree using a struct:

struct Node {

    int data;

    Node* left;

    Node* right;

};

The 'data' variable holds the value of the node, and 'left' and 'right' are pointers to the left and right child nodes, respectively.

Tree Traversal Techniques

Tree traversal refers to visiting each node in a tree exactly once. There are three common traversal techniques:

Pre-order Traversal

In pre-order traversal, the root node is visited first, followed by the left subtree and then the right subtree. Here's the code to perform pre-order traversal:

void preorderTraversal(Node* root) {

    if (root == nullptr)

        return;       

    cout << root->data << " "; // Process the node

    preorderTraversal(root->left); // Traverse left subtree

    preorderTraversal(root->right); // Traverse right subtree

}

In-order Traversal

In in-order traversal, the left subtree is visited first, followed by the root node and then the right subtree. Here's the code to perform in-order traversal:

void inorderTraversal(Node* root) {

    if (root == nullptr)

        return;       

    inorderTraversal(root->left); // Traverse left subtree

    cout << root->data << " "; // Process the node

    inorderTraversal(root->right); // Traverse right subtree

}

Post-order Traversal

In post-order traversal, the left subtree is visited first, followed by the right subtree, and finally the root node. Here's the code to perform post-order traversal:

void postorderTraversal(Node* root) {

    if (root == nullptr)

        return;       

    postorderTraversal(root->left); // Traverse left subtree

    postorderTraversal(root->right); // Traverse right subtree

    cout << root->data << " "; // Process the node

}

Sample Problems

Let's solve some sample problems related to trees:

Problem 1: Count the number of nodes in a binary tree

int countNodes(Node* root) {

    if (root == nullptr)

        return 0;

    return 1 + countNodes(root->left) + countNodes(root->right);

}

Problem 2: Check if a binary tree is symmetric

bool isSymmetric(Node* root) {

    if (root == nullptr)

        return true;

    return isSymmetricHelper(root->left, root->right);

}

bool isSymmetricHelper(Node* leftNode, Node* rightNode) {

    if (leftNode == nullptr && rightNode == nullptr)

        return true;

    if (leftNode == nullptr || rightNode == nullptr)

        return false;

    return (leftNode->data == rightNode->data) &&

           isSymmetricHelper(leftNode->left, rightNode->right) &&

           isSymmetricHelper(leftNode->right, rightNode->left);

}

Problem 3: Find the maximum depth of a binary tree

int maxDepth(Node* root) {

    if (root == nullptr)

        return 0;

    int leftDepth = maxDepth(root->left);

    int rightDepth = maxDepth(root->right);

    return max(leftDepth, rightDepth) + 1;

}

Conclusion

Trees are powerful data structures that enable efficient data organization and retrieval. In this article, we explored the basics of trees, including their terminologies, implementation in C++, and various traversal techniques. By understanding trees and their properties, you can enhance your problem-solving skills in the field of data structures and algorithms.