Rooted Binary Tree: An Overview....

[ Home Page ]  [ Back ]  [ Content of Contributions ]  [ Movement: Green Leaf World ]

 ----------------------------------------------------------------------------------------------------------
Definition :
A binary tree T with N nodes can be defined as,

1. Either, T is empty
2. Or, T has a special node called Root of the tree. All the remaining (N-1) nodes will form two dis-join subset, say LST & RST, called Left Sub-Tree and Right Sub_Tree of T respectively, such that, LST & RST are both binary tree.

A pointer is used to point to the Root node of a tree, as like in the linked list.

 In the above figure, a binary tree has been depicted. TREE_Pointer is pointing to a node, called root node of the tree. It must be assumed that, the origin of the tree is this node. Any operation must be started from this node.

Each node can have at most two child's, called Left child & Right Child. Consider the root node of the tree shown above. It has a left child with data 20 and right child with data 60.

A node may have zero child, it will be called Leaf node. In the above example, nodes with data 30, 40, 70, 90 are leaf nodes.

The node containing data 20, is the root of the Left Sub-tree of the root node with data 10 and similarly, the node containing data 60, is the root of the Right Sub-tree of the root node with data 10.

Level of  tree is very interesting property of a rooted binary tree. The root node is assumed at level 0, it's child's are at level 1, and so on. To make the clear sense, please have a look in the figure below,

The nodes with same parent are called  Siblings.

Path between node n₁ to node n_k is a finite sequence of nodes n₁, n₂,....., n_k such that n_i is the parent of n _i+1 for all i (1 to k-1).

The length of a path is the number of Links(edges) on the path, i.e. number of nodes in the path - 1.

Depth of a node is defined by the length of the path from root to that node. Depth of a tree is the depth of its deepest leaf. Depth of the root is zero.

Height of a node is the longest path from that node to leaf. Height of a tree is the height of its root. Height of any leaf is zero.

Height and Depth  of a tree is equals.

If there is a path from node n_i to node n_j, then node n_i is an ancestor of node n_j and node n_j is a descendant of node n_i.

Full Binary Tree

A binary tree where all the leaf nodes must be in the same level and every internal nodes must have exactly two children's.

 

Complete Binary Tree

A binary tree where all the level are completely filled except possibly the last level, but all the nodes in the last level must be left oriented.

 

Binary Search Tree

A binary tree T, where for every node of T should have value,

1.  >= all the values present in the nodes of its left sub-tree and
2.  < all the values present in the nodes of its right sub-tree

 

Heap Tree

It can be again classified as,

1. Max Heap: A complete binary tree where the root of every sub-tree holds the highest value of the sub-tree.
2. Min Heap: A complete binary tree where the root of every sub-tree holds the lowest value of the
   
   sub-tree.

 

Balanced Binary Search Tree

The main disadvantage of a binary search tree is it's skewed property as shown in the figure below (see  a & b). In Balanced binary search tree the height difference of two sub-tree is limited to 1 maximum for every sub-tree of a binary search tree. It is also called AVL (Adelson, Velskii, Landis) tree as per the name of the inventors. Details will be discussed later.

In the next article we will discuss,

1.  Memory representation of tree and
2.  Tree traversal