Structure of Binary Trees

We learned about trees and binary trees in the following posts:-

• The tree data structure
• The basics of Binary Tree

Now let us try to define the structure of the binary tree. For simplicity, assume that the data of the nodes are integers. One way to represent a node (which contains the data) is to have two links which points to the left and right children along with data fields as shown below:

// Defining the basic structure for a binary tree node

struct binaryTreeNode {
    int data;
    struct binaryTreeNode * left;
    struct binaryTreeNode * right;
};

Please note that in trees, the default flow is from parent to children and showing directed branches is not compulsory. For our discussion, we assume both the representations are same.

Operations on Binary Trees

Basic Operations

• Inserting an element into the tree
• Deleting an element from a tree
• Searching for an element
• Traversing the tree

Auxiliary Operations

• Finding the size of the tree
• Finding the height of the tree
• Finding the level which has the maximum sum
• Finding least common ancestor (LCA) for a given pair of nodes etc..

Applications of Binary Trees

Following are some of the applications where Binary Trees play an important role –

• Expression trees are used in compilers.
• Huffman coding trees which are used in data compression algorithms.
• Binary Search Trees (BST), which support search, insertion and deletion on a collection of items in O(log n) average time.
• Priority Queue (PQ), which support search and deletion of minimum and maximum on a collection of items in logarithmic time (in worst case).