Home » Technical Interview Questions » Tree Interview Questions » Binary Tree Data Structure

# 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

 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: It is the total number of nodes from root to a given node
READ  Find Maximum Level sum in Binary Tree

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= 2H+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 = 2L
READ  Convert Sorted List to Binary Search Tree

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

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions