DS

Binary Tree data structure

Gallery KodeBinary

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

Please find below complete code

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

Advertisements