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 full binary tree with Root as 1.

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 complete binary tree where 3 has only one leaf node.

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 prefect binary tree with root node 1.

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.
Visit right subtree.
void inorder(struct Node* root)
    if(root == NULL)
    cout<<root->data<<" ";

Preorder Traversal

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

Postorder Traversal

Visit left subtree
Visit right subtree
Process root.
void postorder(struct Node *root)
    if(root == NULL)

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}

Please find below complete code

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!.