Table of contents

Introduction to Tree Data Structure

What is a Tree?

A tree is a hierarchical data structure that consists of nodes, with a single node called the root. Each node contains a value and references to its child nodes. Trees are used to represent hierarchical relationships and are widely used in applications like databases, file systems, and searching algorithms.

Representation of a Tree Data Structure

plaintext
          1          <-- Root
         / \
        2   3        <-- Children of root
       / \   \
      4   5   6      <-- Leaf nodes

Key Terminology of a Tree Data Structure

  • Root: The top node of a tree.
  • Node: An element in the tree containing a value.
  • Edge: A link between two nodes.
  • Parent: A node that has one or more children.
  • Child: A node that has a parent.
  • Leaf: A node with no children.
  • Subtree: A tree consisting of a node and its descendants.
  • Depth: The number of edges from the root to a node.
  • Height: The number of edges from a node to the deepest leaf.

Types of Trees

  1. Binary Tree: Each node has at most two children (left and right).
  2. Binary Search Tree (BST): A binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.
  3. Balanced Tree: A tree where the height of the left and right subtrees of any node differ by at most one.
  4. AVL Tree: A self-balancing binary search tree where the difference in heights of left and right subtrees is at most one.
  5. Red-Black Tree: A self-balancing binary search tree with additional properties to ensure balance.
  6. B-Tree: A self-balancing search tree in which nodes can have multiple children, commonly used in databases and file systems.

Key Operations on Trees

  1. Insertion: Adding a node to the tree.
  2. Deletion: Removing a node from the tree.
  3. Traversal: Visiting all the nodes in the tree (in a specific order).
    • Preorder: Visit root, left subtree, right subtree.
    • Inorder: Visit left subtree, root, right subtree.
    • Postorder: Visit left subtree, right subtree, root.
    • Level Order: Visit nodes level by level.

Here are some basic implementations of a binary tree in C++, Java, and Python.

C++ Program to implement a Tree

cpp
#include <iostream>
using namespace std;

// Define a node
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

// Inorder traversal of the tree
void inorderTraversal(Node* root) {
    if (root == nullptr)
        return;
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

// Preorder traversal of the tree
void preorderTraversal(Node* root) {
    if (root == nullptr)
        return;
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// Postorder traversal of the tree
void postorderTraversal(Node* root) {
    if (root == nullptr)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << " ";
}

// Main function
int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

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

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

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

    return 0;
}

Java Program to implement a Tree

java
// Define a node
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

// Main class
public class Main {
    // Inorder traversal of the tree
    void inorderTraversal(Node root) {
        if (root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.data + " ");
        inorderTraversal(root.right);
    }

    // Preorder traversal of the tree
    void preorderTraversal(Node root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    // Postorder traversal of the tree
    void postorderTraversal(Node root) {
        if (root == null)
            return;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.data + " ");
    }

    // Main function
    public static void main(String[] args) {
        Main tree = new 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);

        System.out.print("Inorder Traversal: ");
        tree.inorderTraversal(root);
        System.out.println();

        System.out.print("Preorder Traversal: ");
        tree.preorderTraversal(root);
        System.out.println();

        System.out.print("Postorder Traversal: ");
        tree.postorderTraversal(root);
        System.out.println();
    }
}

Python Program to implement a Tree

python
# Define a node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Inorder traversal of the tree
def inorder_traversal(root):
    if root is None:
        return
    inorder_traversal(root.left)
    print(root.data, end=' ')
    inorder_traversal(root.right)

# Preorder traversal of the tree
def preorder_traversal(root):
    if root is None:
        return
    print(root.data, end=' ')
    preorder_traversal(root.left)
    preorder_traversal(root.right)

# Postorder traversal of the tree
def postorder_traversal(root):
    if root is None:
        return
    postorder_traversal(root.left)
    postorder_traversal(root.right)
    print(root.data, end=' ')

# Main function
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    print("Inorder Traversal: ", end='')
    inorder_traversal(root)
    print()

    print("Preorder Traversal: ", end='')
    preorder_traversal(root)
    print()

    print("Postorder Traversal: ", end='')
    postorder_traversal(root)
    print()

Advantages of Trees

  1. Hierarchical Representation: Naturally represents hierarchical data.
  2. Efficient Searching: Provides efficient searching and sorting operations.
  3. Dynamic Size: Can grow and shrink dynamically as elements are added or removed.

Disadvantages of Trees

  1. Complex Implementation: More complex to implement compared to linear data structures.
  2. Memory Overhead: Requires additional memory for storing references to child nodes.

When to Use Trees

Trees are preferred when:

  • You need to represent hierarchical data.
  • You need to perform quick searches, insertions, and deletions.
  • You need a dynamic data structure that can grow and shrink.

Practice Problems on Trees

  1. Find the Height of a Binary Tree
    • Problem: Given a binary tree, find its height.
    • Example: Input: [1, 2, 3, 4, 5], Output: 3
  2. Check if Two Trees are Identical
    • Problem: Given two binary trees, check if they are identical.
    • Example: Input: [1, 2, 3], [1, 2, 3], Output: True
  3. Level Order Traversal
    • Problem: Perform a level order traversal of a binary tree.
    • Example: Input: [1, 2, 3, 4, 5], Output: [1, 2, 3, 4, 5]
  4. Binary Search Tree Insertion
    • Problem: Insert a node into a binary search tree.
    • Example: Input: [4, 2, 7, 1, 3], node = 5, Output: [4, 2, 7, 1, 3, 5]
  5. Lowest Common Ancestor in a BST
    • Problem: Find the lowest common ancestor of two nodes in a binary search tree.
    • Example: Input: [6, 2, 8, 0, 4, 7, 9], p = 2, q = 8, Output: 6

Frequently Asked Questions (FAQs) on Tree Data Structure

Q1: What is the difference between a tree and a binary tree?

  • A: A tree is a general hierarchical data structure with nodes and edges, while a binary tree is a type of tree where each node has at most two children.

Q2: How is memory managed for trees?

  • A: In most programming languages, memory for trees is dynamically allocated using pointers or references. Each node is typically allocated separately.

Q3: Can trees be implemented without classes?

  • A: Yes, trees can be implemented without classes by using structures (in C/C++) or dictionaries (in Python), but classes often provide a more organized and modular approach.

Q4: What are some common applications of trees?

  • A: Common applications include databases, file systems, syntax trees in compilers, and decision trees in machine learning.

Q5: How do you traverse a tree?

  • A: Tree traversal can be done in various orders: inorder, preorder, postorder, and level order.

Q6: What is the difference between a binary tree and a binary search tree?

  • A: A binary tree is a tree where each node has at most two children. A binary search tree (BST) is a binary tree with the property that the left child contains values less than the parent and the right child contains values greater than the parent.

Q7: What is a balanced tree?

  • A: A balanced tree is a tree where the height of the left and right subtrees of any node differ by at most one, ensuring that the tree remains balanced and operations are efficient.

DSA

Related Articles