Home Theory Structure of Binary Trees

Structure of Binary Trees

by nikoo28
2 comments

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:

structure_of_binary_tree

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

structure_of_binary_tree_1

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

2 comments

anon December 29, 2014 - 19:05

copied from narasimha book?

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

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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