# Binary Tree data structure

A binary tree is a tree data structure with a maximum of two children in each node. Similarly, the recursive meaning of a binary tree is a tree (L, P, R) where L and R are binary trees with P as root.

A binary tree node has pointed to at most another two nodes.

A full binary tree has either 0 or 2 nodes in it.

A complete binary tree is filled with all nodes except the leaf nodes.

For example, a binary tree with height ‘h’ can have 1 to $2^h$ nodes.

A perfect binary tree is a binary tree in which all its nodes filled. Its leaf nodes are exactly $2^h$ nodes. Whereas total nodes are $2^n$.

A balanced binary tree is a binary tree in which the height difference between its left and right children is 1. Any full, complete or perfect binary tree can be a balanced binary tree.

A node representation of any binary tree is as follows. It has an object (which holds data), a left subtree pointer and right subtree pointer.

``````struct Node
{
// Data of the node.
int data;
// Left subtree root node.
struct Node *left;
// Right subtree root node.
struct Node *right;
};``````

### Tree traversal

1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal

Inorder Traversal

``````Visit left subtree.
Process
Visit right subtree.``````
``````void inorder(struct Node* root)
{
if(root == NULL)
return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}``````

Preorder Traversal

``````Process root
Visit left subtree
Visit right subtree``````
``````void preorder(struct Node *root)
{
if(root == NULL)
return;
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}``````

Postorder Traversal

``````Visit left subtree
Visit right subtree
Process root.``````
``````void postorder(struct Node *root)
{
if(root == NULL)
postorder(root->left);
postorder(root->right);
cout<<root->data;
}``````

Let’s take a complete binary tree as shown here, and traverse with the above algorithms.

Below are the traversal results of the above complete binary tree.

``````Pre-Order Traversal: {1, 2, 4, 5, 3, 6, 7}
In-Order Traversal: {4, 2, 5, 1, 6, 3, 7}
Post-Order Traversal: {4, 5, 2, 6, 7, 3, 1}``````

``````Output:
Pre-order :
1  2  4  5  3  6  7
In-order :
4  2  5  1  6  3  7
Post-order :
4  5  2  6  7  3  1``````

Complexity: $O(n)$

This is all about binary trees. If you know anything more about binary trees or you find some error in the codes, please let readers know by commenting below. Cheers!.