Home Theory Structure of Binary Trees

Structure of Binary Trees

by nikoo28
2 comments 3 minutes read

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

You may also like


anon December 29, 2014 - 19:05

copied from narasimha book?

nikoo28 December 29, 2014 - 20:17

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.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More