In this article, we will read about the Binary Tree Data Structure. **Trees** are hierarchical data structures where every node has a parent node except the root node. The nodes with no child are called leaves.

Table of Contents

**Need for Trees?**

1. Trees are used when we need to store data in the form of some hierarchy. Example:- File Systems.

2. Trees like BST provide access in O(logN) complexity which is faster than linked – list.

3. Trees have no defined size and any number of nodes can be added to a Tree data structure.

## Binary tree

A Binary Tree Data Structure is a hierarchical data structure. Tree with at most two children is called a binary tree. Tts two children are generally known as the left and right children.

Binary tree consists of three components:

- Value of the node
- A pointer pointing to the left subtree
- A pointer pointing to the right subtree

Pointer to left child | Value | Pointer to the right child |

If the root is pointing to **NULL **then it is an empty tree.

## Node for Binary Tree Data Structure

struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; };

**Terminologies used in a binary tree**

**Root:**It is a node pointer variable to point to the root node of the tree. when root contains null, the tree is empty.**Leaf:**a node which has zero degrees. It is also called an external node.**Internal node:**Node with at least one child.**Degree:**The total number of children of a node is known as its degree.**Degree of the tree:**the degree of the tree is the maximum degree of all nodes.**Level:**It is the total number of nodes from root to given node -1.**Height of a node:**

Here the integer value in the node of a tree can be replaced by any datatype ex. string, char, array, etc. This is how a tree looks like

TREE 1 <-- root node / \ 2 3 <-- leaf node / 4 <- leaf node

## C++ Code for Binary Tree Data Structure

//C++ Code #include<bits/stdc++.h> using namespace std ; struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; }; /* CreateNode() creates a new node with the given data with NULL left and right pointers. */ TreeNode* CreateNode(int data) { // Allocate memory for new node TreeNode* NewNode = new TreeNode ; // Assign data to this node NewNode->data = data; // Initialize left and right children as NULL NewNode->left = NULL; NewNode->right = NULL; return(NewNode); } int main() { /*create root with data value 1*/ struct TreeNode *root = CreateNode(1); /* following is the tree after above statement 1 / \ NULL NULL */ root->left = CreateNode(2); root->right = CreateNode(3); /* 2 and 3 become left and right children of 1 1 / \ 2 3 / \ / \ NULL NULL NULL NULL */ root->left->left = CreateNode(4); /* 4 becomes left child of 2 1 / \ 2 3 / \ / \ 4 NULL NULL NULL / \ NULL NULL */ return 0 ; }

## Java code for Binary Tree Data Structure

/* Class containing left and right child of current node and key value*/ class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } // A Java program to introduce Binary Tree class BinaryTree { // Root of Binary Tree Node root; // Constructors BinaryTree(int key) { root = new Node(key); } BinaryTree() { root = null; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /*create root*/ tree.root = new Node(1); /* following is the tree after above statement 1 / \ null null */ tree.root.left = new Node(2); tree.root.right = new Node(3); /* 2 and 3 become left and right children of 1 1 / \ 2 3 / \ / \ null null null null */ tree.root.left.left = new Node(4); /* 4 becomes left child of 2 1 / \ 2 3 / \ / \ 4 null null null / \ null null */ } }

## Properties of a Binary Tree Data Structure

- The minimum number of nodes in a binary tree of height H= H + 1.
- Maximum number of nodes in a binary tree of height H= 2
^{H+1}– 1 - Total Number of leaf nodes in a Binary Tree = Total Number of nodes with 2 children + 1
- Maximum number of nodes at any level ‘L’ in a binary tree = 2
^{L}

**SUMMARY**

1. Binary Tree is a tree with at most two children per node.

2. A node with no children is called a leaf and the start node is called the root node.

3. A tree provides operation: access, insertion, deletion faster than that in an array.