*857*

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

## 2 comments

copied from narasimha book?

Hi Anonymous,

Algorithm is a thing you cannot copy. Yes, I have compiled some of the best explanations along with some of my own modifications. :)

Comments are closed.