Binary search tree – it’s traversal and construction for ISC students

Tree is a non linear data structure of representation of nodes. A binary tree can be defined as a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other subsets are themselves binary trees , called the left and right subtree of the original tree. So while adding elements into a tree , we can add them category wise in left and right subtree.

Traversing binary trees

Once you have created a binary tree , you can display it’s contents in several ways. The process of moving through a tree is known as tree traversal. The traversal of a binary tree involves visiting each node in the tree exactly once.There are three popular methods of binary tree traversal – inorder , preorder and postorder traversal . Traversing a binary tree means visiting the root node , it’s left and right subtrees. The only difference among the methods is the order in which these three operations are performed.

To traverse a binary tree in inorder , we perform the following operations :-

1.Traverse the left subtree inorder
2.Visit the root.
3.Traverse the right subtree inorder.

To traverse a tree in preorder

1.Visit the root.
2.Traverse the left subtree in preorder
3.Traverse the right subtree in preorder

To traverse a tree in postorder

1.Traverse the left subtree in postorder
2.Traverse the right subtree in postorder
3.Visit the root.

Steps for constructing a binary tree having preorder sequence as A,B,C,D,E and inorder sequence B,A,D,C,E

In such case always read the root from preorder and sub trees from inorder. In preorder traversal, root of the tree is visited first, so ‘A’ is the root. Again in inorder traversal, top most root is visited after visiting the left sub tree. We can easily mark the left sub tree and right sub tree of the tree. In the above case from preorder sequence we find that ‘A’ is the root and from the inorder sequence it is clear that left sub tree has only one node ‘B’ and right sub tree has the nodes ‘D’, ‘C’, ‘E’.

In preorder traversal of tree, after visiting the root, left subtree is visited. Here ‘B’. In inorder sequence only ‘B’ is there at the left of root ‘A’.
Again in preorder, next node visited is ‘C’, and in the inorder sequence, position of ‘C’ is between ‘D’ and ‘E’.

In this style we have to find out the root from preorder sequence and left and right sub trees from inorder sequences.