Binary Tree Code Implementation

Board Infinity
Board Infinity
Binary Tree Code Implementation

    Data Structures: Foundation of Effective Programming

    10 Common Data Structures Every Programmer Must Know

    Quick Guide to Abstract Data Types

    A Simple Introduction to Recursion

    Arrays vs Linked List

    Stack in Data Structure

    Complete Walkthrough of Stacks in Data Structure

    Working on Queue using STL

    Implementing Queue using Stacks

    A Detailed walkthrough of the Doubly Linked List

    How to Reverse a Linked List?

    Binary Tree Code Implementation

    Complete Walkthrough of AVL Trees

    Heap Data Structure

    Trie Data Structure: Explanation and Examples

Introduction

Do you know what a binary is? How can we implement binary trees in our favorite programming language? Then don't worry, dear, when Board Infinity is here.

In this article, we will discuss each and everything about the binary tree. We will also look at its implementation and its properties. Let us understand what it is.

What is a Binary Tree?

Each parent node can have a maximum of two children in a binary tree, a type of tree data structure. A binary tree's nodes are made up of these three components:

  • Data item
  • Address of the left child
  • Address of the right child

Let us look at the types of a binary trees.

Types

The types of binary trees are mentioned below:

  1. Full Binary Tree: An exceptional form of a binary tree called a full binary tree includes either two offspring or none at all for each parent node and internal node.
  2. Perfectly Binary Tree: A type of binary tree known as a perfect binary tree is one in which every leaf node is at the same level, and every internal node has exactly two child nodes.
  3. Complete Binary Tree: A complete binary tree is identical to a complete binary tree, with two key exceptions.
  4. Each level must be fully filled.
  5. Each component of the leaf must slant to the left.
  6. A complete binary tree does not necessarily have to be a full binary tree because the final leaf element may not have the right sibling.
  7. Degenerate or Pathological Tree: A degenerate or pathological tree is one that only has one offspring, either to the left or to the right.
  8. Skewed Binary Tree: A skewed binary tree is a diseased or degenerative tree in which the right or the left nodes predominate. There are two kinds of skewed binary trees: left-skewed binary trees and right-skewed binary trees.
  9. Balanced Binary Tree: It is a kind of binary tree in which each node has a height difference between the left and right subtrees that is either 0 or 1.

Let us discuss the applications of binary trees.

Applications

The applications of binary trees are mentioned below:

  • In router algorithms,
  • For rapid and simple access to data
  • To use the syntax tree
  • To implement the heap data structure

Now we understand what a binary tree is. So, let us discuss how we can implement the binary tree. Let us look at binary tree code.

Implementation of Binary Tree

Before moving on to the binary tree code, let us look at the representation of the binary tree. A structure that includes two pointers to additional structures of the same type and a data part represents a node in a binary tree.

struct treeNode
{
 int myData;
 struct treeNode *leftNode;
 struct treeNode *rightNode;
};

Here is the implementation of binary tree code.

// Binary Tree Code in C++

#include <stdlib.h>

#include <iostream>

using namespace std;

struct treeNode
{
    int myData;
    struct treeNode *leftNode;
    struct treeNode *rightNode;
};

// Creating a new node
struct treeNode *newNode(int myData)
{
    struct treeNode *treeNode = (struct treeNode *)malloc(sizeof(struct treeNode));

    treeNode->myData = myData;

    treeNode->leftNode = NULL;
    treeNode->rightNode = NULL;
    return (treeNode);
}

// PreorderTraversal
void traversePreOrder(struct treeNode *temp)
{
    if (temp != NULL)
    {
        cout << " " << temp->myData;
        traversePreOrder(temp->leftNode);
        traversePreOrder(temp->rightNode);
    }
}

// InorderTravesal
void traverseInOrder(struct treeNode *temp)
{
    if (temp != NULL)
    {
        traverseInOrder(temp->leftNode);
        cout << " " << temp->myData;
        traverseInOrder(temp->rightNode);
    }
}

// PostorderTraversal
void traversePostOrder(struct treeNode *temp)
{
    if (temp != NULL)
    {
        traversePostOrder(temp->leftNode);
        traversePostOrder(temp->rightNode);
        cout << " " << temp->myData;
    }
}

int main()
{
    struct treeNode *rootNode = newNode(2);
    rootNode->leftNode = newNode(3);
    rootNode->rightNode = newNode(4);
    rootNode->leftNode->leftNode = newNode(5);

    cout << "preorder traversal: ";
    traversePreOrder(rootNode);
    cout << "\nInorder traversal: ";
    traverseInOrder(rootNode);
    cout << "\nPostorder traversal: ";
    traversePostOrder(rootNode);
}

Output

preorder traversal:  2 3 5 4
Inorder traversal:  5 3 2 4
Postorder traversal:  5 3 4 2

write your code here: Coding Playground

Conclusion

In this article, we have discussed binary tree code. We have also discussed what a binary tree is and what its applications are. We discussed its several types. Binary trees are an important part of tree data structure and have many real-world applications.