Binary Tree Data Structure

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.

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:

1. Value of the node
2. A pointer pointing to the left subtree
3. A pointer pointing to the right subtree

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: It is the total number of nodes from root to a given 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

1. The minimum number of nodes in a binary tree of height H= H + 1.
2. Maximum number of nodes in a binary tree of height H= 2^H+1 – 1
3. Total Number of leaf nodes in a Binary Tree = Total Number of nodes with 2 children + 1
4. 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.

References