Concept of Binary Tree

Before start talking about the binary tree, let’s clear the concept of the tree. So, what is a tree in programming? A tree is a collection of elements called nodes. Each node contains some value or element. Node is the main component of any tree structure and it stores the actual data along with links to other nodes.

Tree Terminologies

Root - Root is the unique node in the tree structure in which further subtrees were attached. A root node has its child that are left child and right child. In the given figure A is the root node.

Degree of Node - The total number of subtree attached to that node is called the degree of the node. For node A the degree is 3, for node E the degree is 0.

Leaf Nodes - These are the terminals nodes of the tree. The nodes which have degree 0 are called as leaf nodes of the tree. These nodes are always present at the end of the tree. Here in our example E, F, C, G, H are the leaf nodes.

Internal Nodes - Internal Nodes are other than leaf nodes and the root node. These nodes are present in between root node and leaf nodes. Here, B and D are internal nodes.

Parent Node - The Parent Node having sub-branches. In the above figure node B is the parent node of E, F, and G where E, F, G are called children of B.

Predecessor - The predecessor of the other node means some particular nodes represent previously to other nodes. In the example, the node E is the predecessor of node B.

Successor - The node which occurs next to some other node is called successor of that node. In the example, B is successor of E, F, and G.

Level of tree - The root node is always considering at level zero, and its adjacent children are supposed to be at level 1 and so on. In the example, the node A is at level 0, the node B, C, D are at level 1, the nodes E, F, G, H are at level 2.

Height of the tree - The maximum level represents the height of the tree. Here in the example, the height of the tree is 3. The height of the tree is also called depth of the tree.

Forest - A tree may be considered a forest in which has only a single node or root and has no predecessor of any forest.

Degree of tree - The maximum degree of the node in the tree is called the degree of the tree. Here, the degree of tree is 3.

Let’s back to the main topic the Binary Tree -

Binary tree

A binary tree is a tree data structure where each node has up to two child nodes. The two children are usually called the left and right nodes. Parent nodes are connected with children, while child nodes include references to their parents. That means, a binary tree is a non-linear data structure and each node has not more than two child.

Advantages of Binary Tree

• Searching in Binary tree become faster and it provides six traversals.

• Two of six traversals give the sorted order of elements.

• Maximum and minimum elements can be directly picked up.

• It is used for graph traversal and to convert an expression to postfix and prefix forms.

Basic Operations

Insert

The very first insertion is created the tree. Then locate its proper location before insert an element. Start searching from the root node, if the data is less than the key value, then search for the empty location in the left subtree and insert the data or search for the empty location in the right subtree and insert the data.

Logic -

/* Insertion */
if x = nil then return "Error"
y = x
while true do {
    if key[y] < k
        then z = left[y]
    else z = right[y]
        if z = nil break
}
if key[y] > k then left[y] = z
else right[p[y]] = z

Search

When search for an element, start from the root node. Search for the element in the left subtree if the data is less than the key value, otherwise, search in the right subtree. Follow the same algorithm for each node.

Logic -

/* Search */
y = x
while y != nil do
    if key[y] = k then return y
    else if key[y] < k then y = right[y]
    else y = left[y]
return ("NOT FOUND")
 

In-order Traversal

In this traversal, the left subtree is visited first, then the root and later the right subtree. But always remember that every node may represent a subtree itself. If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

Logic -

// InOrder traversal algorithm
inOrder(TreeNode<T> n) {
      if (n != null) {
          inOrder(n.getLeft());
          visit(n)
          inOrder(n.getRight());
      }
}

Pre-order Traversal

In this traversal, the root node is visited first, then the left subtree and finally the right subtree.

Logic -

void preorder( BTREE__NODE_p_t node )
   if ( node != NULL )
       visit( node )
       preorder( node->left )
       preorder( node->right )

Post-order Traversal

In this, the root node is visited last, hence the name. First, we traverse the left subtree, then the right subtree and finally the root node.

Logic -

void postorder( BTREE__NODE_p_t node )
   if ( node != NULL )
       postorder( node->left )
       postorder( node->right )
       visit( node )

Deletion

Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.

Logic -

/* Delete */
if left[z] = nil or right[z] = nil
    then y = z
else y = BST-Successor(z)
    y is the node that's actually removed.
    Here y does not have two children.
if left[y] != nil
    then x = left[y]
else x = right[y]
    x is the node that's moving to y's position.
if x != nil then p[x] = p[y]
    p[x] is reset If x isn't NIL.
    Resetting is unnecessary if x is NIL.
if p[y] = nil then root[T] = x
    if y is the root, then x becomes the root.
    Otherwise, do the following.
else if y = left[p[y]]
    then left[p[y]] = x
    if y is the left child of its parent, then
        Set the parent's left child to x.
    else right[p[y]] = x
        If y is the right child of its parent, then
        Set the parent's right child to x.
    if y != z then {
        key[z] = key[y]
        Move other data from y to z
    }
return (y)

Types of Binary tree

There are different types of binary trees. Those are -

Complete Binary Tree

A binary tree is said to be a complete binary tree if all its levels, except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible.

Strictly Binary Tree

When every none leaf node in a binary tree is filled with left and right subtrees, the tree is called a strictly binary tree.

Extended Binary Tree

The binary tree that is extended with no nodes or left or right node or both the nodes is called an extended binary tree or a 2- tree. The extended nodes are indicated by the square box. If maximum nodes in the binary tree have one child (nodes) shown at either left or right by adding one or more children, then tree also can be extended. This binary tree is very useful for representation of algebraic expressions. The left and right child nodes denote operands and parent node indicates operator.

Full Binary Tree

A Binary Tree is full binary tree only if each non-leaf node has exactly two child nodes and all leaf nodes are at the same level.

Usage of binary tree

• It can be used to represent arithmetic expressions.

• It used in Unix kernels for managing a set of virtual memory areas.

• It used to efficiently store data in sorted form in order to access and search stored elements quickly.

• Binary trees use for Binary Space Partition which used in almost every 3D video game to determine what objects need to be rendered.

• Binary tree used in almost every high-bandwidth router for storing routing table.

• Hash Trees used in p2p programs and specialized image-signatures in which a hash needs to be verified.

• Binary Search Tree used in many search applications where data is constantly entering/leaving.

• Heaps used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems.

• Huffman Coding Tree (Chip Uni) used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.

• GGM Trees used in cryptographic applications to generate a tree of pseudo-random numbers.

• Syntax Tree constructed by compilers and (implicitly) calculators to parse expressions.

• Treap randomized data structure used in wireless networking and memory allocation.

• Decisions have made on the basis of evidence and things that might occur randomly, and conclusions to reach. Binary tree used to draw these in each separate shape of node.