Data Structure : Tree traversal algorithm

We have discussed tree and binary tree in our last post part1 and part2. We discussed most common operations on Tree and Binary Tree. In this post we will discuss Tree traversal.

Traversing a tree mean visiting each node in specified order. Traversing is not as commonly used as find, insert and delete operations. It is not fast, but is very useful in some situation. There are three simple orders in which tree can be transferred: Inorder, Preorder and Postorder. We will discuss these traversing orders only.

Inorder Traversal

This is the most commonly used traversal order for Binary tree. An inorder traversal of binary tree will cause all the nodes to be visited in ascending order.  This is useful when you need to create a sorted list of data in a binary tree. Simplest way to execute traversal is through recursion. Below are the three steps to implement inorder traversal

1. Visit node’s left sub tree
2. Visit node
3. Visit node’s right sub tree

Jave code for inorder traversal is

private void inOrder(Node node)

{

if(node != null)

{

inOrder(node.leftChild);

System.out.print(node.getValue() + “ “);

inOrder(node.rightChild);

}

}

Preorder and Postorder Traversal

These are almost same as inorder traversal; only the sequence of traversing node, left subtree and right subtree is different. These are used generally in parsing and analysing expression like algebra expression.

Below are the steps to execute preorder traversal

1. Visit node
2. Visit node’s left sub tree
3. Visit node’s right sub tree

Java code for prorder traversal is

private void preOrder(Node node)

{

if(node != null)

{

System.out.print(node.getValue() + “ “);

preOrder(node.leftChild);

preOrder(node.rightChild);

}

}

Similarly, below are the steps to execute postorder traversal

1. Visit node’s left sub tree
2. Visit node’s right sub tree
3. Visit node

Java code for postorder traversal is

private void postOrder(Node node)

{

if(node != null)

{

postOrder(node.leftChild);

postOrder(node.rightChild);

System.out.print(node.getValue() + “ “);

}

}

Data Structure: Tree and Binary Tree: Part 2

In the part 1, we discussed Tree in brief. In this part, we will discuss Binary Tree. Binary Tree has two additional constraints in addition to what regular tree has. Any node in Binary Tree should not have more than 2 children. Value at the left child should always be lesser than parent’s value and value at the right child should not be lesser than parent’s value. Only these two additional characteristics make any tree a Binary Tree.  Here is the basic Java code of Tree Node

class Node

{

Int value;

node leftChild;

node rightChild;

}

We will discuss 3 common operations of Binary Tree.

1. Find
2. Insert
3. Delete

Find

Finding a node with a specific key is the simplest all the 3 major operation. Start from root and traverse down the tree until key is found or leaf node is reached. Here are three steps to

1. Check the value of current node, if value is same as search key, return location.
2. If value of current node is greater than search key, go to the left sub-tree
3. If value of current node in lesser than search key, go to right sub-tree.

Start with setting root as current, execute the above three steps unless leaf node is hit or value has been found. If program hits leaf node traversing down the tree searching for key, it means search key not found.

public Node findValnode(int value)

            {

                        Node current = root;

                       

                        while(current != null)

                        {

                                    if(current.getValue() == value)

                                    {

                                                return current;

                                    }

                                    else if(value < current.getValue())

                                                current = current.getLeftChild();

                                    else

                                                current = current.getRightChild();

                                               

                        }

                        return null;

            }

Insert

To insert a node, we must find place to insert the node. Insertion is almost same as finding a node. Take value to insert as search key and insert the value at found place. If value is not found in the tree, it will be added to any leaf node as either left child or right child depending upon its value. Even if value is found and duplicate is allowed in tree, it will be added in right sub-tree to the found node. Below are the steps to insert a node.

1. Create a node with the given value
2. Search the given value in the tree.
3. Insert the node as left child/ right child, depending upon its value, to the leaf node where Tree Traversing ended.

Below is the java code for Insertion in tree.

public void insert(int value)

            {

                        Node node = new Node();

                        node.setValue(value);

                       

                        if(root == null)

                        {

                                    root = node;

                                   

                        }

                        else

                        {

                                    Node current = root;

                                    Node parent = root;

                                    while(true)

                                    {

                                                parent = current;

                                                if(value < current.getValue())

                                                            current = current.getLeftChild();

                                                else

                                                            current = current.getRightChild();

                                               

                                               

                                                if(current == null && value < parent.getValue())

                                                {

                                                            parent.setLeftChild(node);

                                                            break;

                                                }

                                                else if(current == null && value >= parent.getValue())

                                                {          

                                                            parent.setRightChild(node);

                                                            break;

                                                }

                                               

                                    }

                        }

            }

Delete

Delete is the most complicated common operation of Binary Tree. First find the node to delete, use same approach as for Find operation. Once the node is found, there are three cases to consider before deleting the node

Case 1.             The node to be deleted is leaf node

Case 2.             The node to be deleted has only one child

Case 3.             The node to be deleted has two children

Case 1: It is simplest of all above cases. To delete a leaf node, change the appropriate child field in node’s parent to null

Case 2:  This case is also not that complicated. Node to be deleted has only two connections: one to its parent and second to its child. To delete the node, just remove the node from the sequence. Connect the node’s parent directly to its child.

Case 3: This is little tricky and complicated. If the deleted node has 2 children, we cannot just replace it with one of these children. There are various cases to consider.

Good news is there is trick to handle these cases. Find the inorder successor of the node to be deleted.  Literally speaking, inorder successor is the next highest value in the tree. It means, this successor should be in the right sub tree of the node to be deleted. For sake of information, inorder, preorder and postorder are the three ways a binary tree can be traversed. We will discuss the Tree Traversal Algorithms in detail in some other post. For this post, let not digress from the main topic and let keep this post simple. Here is java code to find inorder successor of a node (This is just for reference)

private Node getSuccessor(Node delNode)

            {

                        Node successorParent = delNode;

                        Node successor = delNode;

                        Node current = delNode.getRightChild();

                        while(current != null)

                        { // left children,

                                    successorParent = successor;

                                    successor = current;

                                    current = current.getLeftChild();

                        }

                        // if successor not

                        if(successor != delNode.getRightChild()) // right child,

                        { // make connections

                        successorParent.setLeftChild(successor.getRightChild());

                        successor.setRightChild(delNode.getRightChild());

                        }

                        return successor;

            }

Once we have successor in hand, there are two cases to handle to delete the node.

Successor is the right child of the node to be deleted

If the successor is the right child of the node to be deleted, then this right child does not have left child. Let refer node to be deleted as current node. The deletion can be done in two steps

1. Remove reference to current from its parents and set reference to successor in that place
2. Set successor left child to point to current’s left child.

Successor Is Left Descendant of Right Child of the node to be deleted

If the successor is the left descendant of right child of the node to be deleted, deletion takes place in four steps. Let refer node to be deleted as current node.

1. Plug the right child of the successor into the left child of its parent.
2. Plug the right child of the current to the right child of its successor
3. Unplug current node from the its parent and set successor in that place
4. Unplug left child of the current and set it into successor left child

Data Structure : Tree and Binary Tree: Part 1

In the last post we discussed Advance Sorting, an algorithm; we are shifting back our focus to data structure. The fundamental data storage structure used in programming language: Binary Tree. If you are wondering why discuss one more data storage structure when we know two data storage array and linked list, you will get the answer by end of this post.

There is an issue with array, specially ordered array: Slow insertion. Steps you need to insert a new data in ordered array are

1.      Search for the right place: An ordered array can be quickly searched using binary search algorithm. Compare the new data with the value in the middle of array, if it is less narrow your search to top half of the array. Repeatedly executing the process will complete the search in O(log N) time.

2.      Create Space: Shift all the data 1 block to the right of identified place to create space for new record. This is very time consuming steps.

3.     Now insert the data.

Step 2 & 3 are the reasons, insertion is slow in ordered array. This insertion issue is tackled using linked list as data structure. Insertion and deletion in linked list require O(1)  as insertion and deletion in linked list is accomplished by changing references.

Unfortunately, finding a data in linked list is not so easy. You have to start at the beginning of the list and visit each element until you find the right place/data. Even an ordered list cannot help, you have to start at the beginning and visit each element in order.

So is there any data structure with quick insertion and deletion of linked list and also quick searching of an ordered array?

 Yes, Binary Tree.

Before, we start discussing Binary Tree, lets go through from some basics of Tree

Tree is collection of nodes connected by edges. Nodes represent the value and edges between the nodes represent the way nodes are related. Conventionally nodes are represented by bubbles or circles and edges are represented by lines.

Below diagram presents the tree terminology

Root – Root is a node which does not have any parent.

Parent – Node in the tree that is one step higher in hierarchy and lying on the same branch

Child – As in the diagram above: B & C are the child of A, D & E are the child of B and F & G are the child of C. A child is node which is directly linked with its parent and it is below parent in structure. Data structure tree is upside down version of actual tree. Root on top, branches growing downward and leaf at the bottom.

Sibling – Nodes that share same parent. As in the diagram above D & E are siblings

Leaf – Nodes without children are called leaf node.

We will discuss rest in next week.