4 A Binary tree is a non-linear data structure in which each node has maximum of two child nodes. The tree connections can be called as branches.

4 Binary tree provides six traversals, which include

*“in order”, “post order” and “pre order” traversals.*4 Inorder gives us elements in ascending order

__In order traversal:__

In order traversal follows LVR method (L- left, V- visit vertex, R- right). This order gives sorted order in ascending order.

1. Move to the root node of a tree.

2. Move to its left node if exists.

3. Repeat the second step till a node with no left encounters.

4. Now, print the element and move to right if it exists.

5. Repeat the above three steps for all pending-nodes in a stack manner.

LVR(tree t)

{

if(t)

{

LVR(t.left);

System.out.println(t.x);

LVR(t.right);

}

}

__Pre order traversal:__

Pre order traversal follows VLR method

1. Move to the root node of a tree.

2. Print the element and move to left node if exists.

3. Repeat the second step till a node with no left encounters.

4. Now, move to right if it exists and print element.

5. Repeat the above three steps for all pending-nodes in a stack manner.

VLR(tree t)

{

if(t)

{

System.out.println(t.x);

VLR(t.left);

VLR(t.right);

}

}

__Post order traversal:__

Post order traversal follows LRV method

1. Move to the root node of a tree.

2. Move to left node if exists.

3. Repeat the second step till a node with no left encounters.

4. Now, move to right if it exists.

5. Repeat from step 2 till a node with no left and no right encounters.

6. Print the element.

7. Repeat the above three steps for all pending-nodes in a stack manner.

LRV(tree t)

{ if(t)

{

LRV(t.left);

LRV(t.right);

System.out.println(t.x);

}

}

40 |

56 |

48 |

35 |

28 |

Binary Tree |

__Example:__

A binary tree is shown for the elements

*40, 56, 35, 48, 22, 65, 28*

__In order (LVR):__22, 28, 35, 40, 48, 56, 65

__Pre order (VLR):__40, 35, 22, 28, 56, 48, 65

__Post Order (LRV)__: 28, 22, 35, 48, 65, 56, 40

## 0 comments:

## Post a Comment