Binary Tree Traversal

Traversal of a tree means stepping through the nodes of a tree by means of the connections between parents and children, which is also called walking the tree.

There are many operations that are often performed on a tree such as search a node, print some information, insert a node, delete a node, and so on. All such operations need the traversal through a tree.

There are several traversal methods such as

            i) Inorder traversal

            ii) Postorder traversal

            iii) Preorder traversal

Inorder Traversal

In this traversal, the left subtree is visited first in inorder followed by the root and then the right subtree in inorder.

Algorithm

1. Traverse the left subtree of the root node in inorder.

2. Visit the root node node.

3. Traverse the right subtree of the root node in inorder.

Postorder Traversal

In this traversal, the left subtree is visited first in postorder followed by the right subtree

in postorder and then the root.

Algorithm

1. Traverse the root’s left child (subtree) of the root node in postorder.

2. Traverse the root’s right child (subtree) of the root node in postorder.

3. Visit the root node.

Preorder Traversal

In this traversal, the root is visited first followed by the left subtree in preorder and then the right subtree in preorder.

Algorithm

1. Visit the root node, say D.

2. Traverse the left subtree of the node in preorder.

3. Traverse the right subtree of the node in preorder.

Linked Implementation of Binary Trees

Binary tree has a natural implementation in a linked storage. Each node of a binary tree has both a left and a right subtree. Each node will have three fields—Lchild, Data, and Rchild.

 

In this node structure, Lchild and Rchild are the two link fields to store the addresses of left child and right child of a node; data is the information content of the node.

 

Here, 0 (zero) stored at Lchild or Rchild fields represents that the respective child is not present.

Advantages

The merits of representing binary trees through liked representations are as follows:

1. Like sequential representation, memory is not wasted.

2. Insertion and deletion operations are more efficient.

3. It is useful for dynamic data.

Disadvantages

The demerits of representing binary trees through linked representation are as follows:

1. In this representation, there is no direct access to any node. It has to be traversed from the root to reach to a particular node.

2. Having two link fields require more memory of node.

3. The programming languages not supporting dynamic memory management would not be useful for this representation.

Insertion of a node in Binary tree

The node to be inserted could be a branch node or a leaf node.

The insertion procedure is a two-step process:

1. Search for the node whose child node is to be inserted. This is a node will be parent node at level i, and a node is to be inserted at the level i + 1 as either its left child or right child.

2. Link a new node to the node that becomes its parent node, that is, either the Lchild or the Rchild.

Ex: Insertion of node G as the Rchild of node F

Array Implementation of Binary Trees

One of the ways to represent a tree using an array is to store the nodes level-by-level, starting from the level 0.

Let us consider the complete binary tree

Disadvantages

The various demerits when representing binary trees using arrays are as follows:

1. Other than full binary trees, majority of the array entries may be empty.

2. Dynamic resizing of array is not possible.

3. Insertion and deletions of new nodes is inefficient. ( Requires considerable data movement up and down the array, which demand excessive amount of processing time.)

Advantages

The various merits of representing binary trees using arrays are as follows:

1. Any node can be accessed from any other node by calculating the index.

2. No use of pointers.

Binary Tree

A binary tree

1. is either an empty tree or

2. consists of a node, called root, and two children, left and right, each of which is itself a binary tree.

 

Properties of a Binary Tree

1. There exists a unique path between every two vertices.

2. The number of vertices is one more than the number of edges in the tree. That is e = v-1

3. The sum of degrees of the vertices in any graph is equal to 2e. That is 2e=2v-2

4. The maximum number of nodes of level i in a binary tree is 2ⁱ⁻¹, where i ≥ 1.

5. The maximum number of nodes of depth d in a binary tree is 2^d−1, where d ≥ 1.

Binary Tree Abstract Data Type

class TreeNode

{

public:

char Data;

TreeNode *Lchild;

TreeNode *Rchild;

};

 

class BinaryTree

{

private:

TreeNode *Root;

public:

BinaryTree(){Root = Null};

// constructor creates an empty tree

TreeNode * GetNode();

void InsertNode(TreeNode*);

void DeleteNode( TreeNode*);

};

 

The basic operations on a binary tree can be as listed as follows:

1. Creation—Creating an empty binary tree to which the ‘root’ points

2. Traversal—Visiting all the nodes in a binary tree

3. Deletion—Deleting a node from a non-empty binary tree

4. Insertion—Inserting a node into an existing (may be empty) binary tree

5. Merge—Merging two binary trees

6. Copy—Copying a binary tree

7. Compare—Comparing two binary trees

8. Finding a replica or mirror of a binary tree

 

Realization of a Binary Tree

The implementation of a binary tree should represent the hierarchical relationship between a parent node and its left and right children.

Binary tree can be implemented as

-          Array implementation of a Binary tree

-          Linked implementation of a Binary tree