Full Binary Tree | DSA in C++ - Software Development PDF Download

Introduction to Full Binary Trees

In the field of data structures and algorithms, binary trees play a vital role. A binary tree is a hierarchical structure that consists of nodes, where each node can have at most two children, referred to as the left child and the right child. One special type of binary tree is a full binary tree. In this article, we will explore the concept of a full binary tree, understand its properties, and learn how to implement it in C++.

What is a Full Binary Tree?

A full binary tree is a binary tree in which all nodes, except the leaf nodes, have exactly two children. In other words, every node in a full binary tree has either zero or two children. The leaf nodes are the nodes that do not have any children.

Properties of Full Binary Trees

• The total number of nodes in a full binary tree can be expressed as a power of 2, i.e., 2^{h - 1}, where 'h' is the height of the tree.
• The height of a full binary tree with 'n' nodes is log2(n+1) - 1.
• The number of leaf nodes in a full binary tree is (n+1)/2, where 'n' is the total number of nodes.

Implementing a Full Binary Tree in C++

To implement a full binary tree in C++, we need to define a node structure and write functions to perform various operations on the tree. Let's start with the node structure:

struct Node {

    int data;

    Node* left;

    Node* right;

};

Creating a Full Binary Tree

To create a full binary tree, we can use a recursive approach. We will create a function that takes the data for the current node, creates a new node, and recursively calls itself to create the left and right children.

Node* createFullBinaryTree(int data) {

    Node* newNode = new Node();

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

Let's create a full binary tree with the following structure:

        1

       / \

      2   3

     / \

    4   5

Node* root = createFullBinaryTree(1);

root->left = createFullBinaryTree(2);

root->right = createFullBinaryTree(3);

root->left->left = createFullBinaryTree(4);

root->left->right = createFullBinaryTree(5);

Traversal Operations on Full Binary Trees

Preorder Traversal

Preorder traversal visits the nodes in the order: root, left subtree, right subtree.

void preorderTraversal(Node* node) {

    if (node == NULL)

        return;

    cout << node->data << " ";

    preorderTraversal(node->left);

    preorderTraversal(node->right);

}

Output for the above full binary tree:

1 2 4 5 3

Inorder Traversal

Inorder traversal visits the nodes in the order: left subtree, root, right subtree.

void inorderTraversal(Node* node) {

    if (node == NULL)

        return;

    inorderTraversal(node->left);

    cout << node->data << " ";

    inorderTraversal(node->right);

}

Output for the above full binary tree:

4 2 5 1 3

Postorder Traversal

Postorder traversal visits the nodes in the order: left subtree, right subtree, root.

void postorderTraversal(Node* node) {

    if (node == NULL)

        return;

    postorderTraversal(node->left);

    postorderTraversal(node->right);

    cout << node->data << " ";

}

Output for the above full binary tree:

4 5 2 3 1

Sample Problems

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

int countLeafNodes(Node* node) {

    if (node == NULL)

        return 0;

    if (node->left == NULL && node->right == NULL)

        return 1;

    return countLeafNodes(node->left) + countLeafNodes(node->right);

}

Problem 2: Determine if a binary tree is a full binary tree.

bool isFullBinaryTree(Node* node) {

    if (node == NULL)

        return true;

    if (node->left == NULL && node->right == NULL)

        return true;

    if (node->left != NULL && node->right != NULL)

        return isFullBinaryTree(node->left) && isFullBinaryTree(node->right);

    return false;

}

Conclusion

In this article, we learned about full binary trees and their properties. We explored how to implement a full binary tree in C++ and perform traversal operations on it. Understanding full binary trees is crucial as they find applications in various algorithms and data structures. By practicing the provided sample problems, you can deepen your understanding and enhance your problem-solving skills.