Home Theory Structure of Binary Trees

# Structure of Binary Trees

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

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