Let Others Too Know

Post Order Traversal In Binary Tree Its LRN ordered traversal. The order goes this way: L: Traverse the left sub tree. R: Traverse the right sub tree. N: visit the node Lets check with an example. Consider the following example. Traverse the left sub tree of node 1 Traverse the left sub tree of node 2 Visit the node 4 Traverse the right sub tree of node 2 Visit the node 5 Visit the node 2 Traverse the right sub tree of node 1 Traverse the left subtree of node 3 Visit the node 6 Traverse the right sub tree of node 3 Visit the node 7 Visit the node 3 Visit the node 1 On completing the traversal we get the post order if we follow the bolded nodes. Post Order: 4 , 5 , 2 , 6 , 7 , 3 , 1

In Order Traversal In Binary Tree Its LNR ordered traversal. The order goes this way: L: Traverse the left sub tree. N: visit the node R: Traverse the right sub tree. Lets check with an example. Consider the following example. Traverse the left sub tree of node 1 Traverse the left sub tree of node 2 Visit the node 4 Visit the node 2 Traverse the right sub tree of node 2 Visit the node 5 Visit the node 1 Traverse the right sub tree of node 1 Traverse the left subtree of node 3 Visit the node 6 Visit the node 3 Traverse the right sub tree of node 3 Visit the node 7 On completing the traversal we get the in order if we follow the bolded nodes. In Order: 4 , 2 , 5 , 1 , 6 , 3 , 7

Pre Order Traversal In Binary Tree Its NLR ordered traversal. The order goes this way: N: visit the node L: Traverse the left sub tree. R: Traverse the right sub tree. Lets check with an example. Consider the following example. Visit the node 1 Traverse the left sub tree of node 1 Visit the node 2 Traverse the left sub tree of node 2 Visit the node 4 Traverse the right sub tree of node 2 Visit the node 5 Traverse the right sub tree of node 1 Visit the node 3 Traverse the left subtree of node 3 Visit the node 6 Traverse the right sub tree of node 3 Visit the node 7 On completing the traversal we get the pre order if we follow the bolded nodes. Pre Order: 1 , 2 , 4 , 5 , 3 , 6 , 7

Traversal In Binary Tree Traversing a binary tree means visiting each node of the tree exactly once. At each node : N : Visit the node L : Traverse its left subtree R : Traverse its right subtree These actions can be performed in any order... (3! = 6 different ways of ordering the three tasks.) Different orders: NRL NLR LNR LRN RNL RLN But we follow the convention which states left subtree to be traversed before right sub tree. Thus we are left with three orders: NLR , LNR and LRN The orders are named according the position of the node i.e., position of N in the order. pre : NLR in  : LNR post : LRN PRE ORDER TRAVERSAL: ( NLR ) N : Visit the node L : Traverse the left subtree R : Traverse the right subtree IN ORDER TRAVERSAL: ( LNR ) L : Traverse the left subtree N : Visit the node R : Traverse the right subtree ...

Trees - 2 Types: Strictly binary tree: Degree is every node either 0 or 2. Full Binary tree: Degree of every node is 2. Complete Binary Tree:A binary tree in which every level , exccept possibly the last , is completely filled and all nodes are as far left as possible. Array Representation of binary tree: Also called as sequential representation or linear representation We use 1D array Store the data with indexed 1 i.e., root node at Array[1](Even we can use 0 based index ) If a node is at index k in the array, its left child is at index 2k and right child at index 2k+1. If a node at index k then its parent is at index floor(k/2) The size of array needed to store a tree of height h is 2 h -1 Linked list representation : struct node { struct node *left; struct node *right; int data; } This structure can be used for the binary tree. Self referential structure where first and second...

Trees The data is organised in a hierarchial manner. Terminology: Node Edges Parent Node Child Node Leaf Node Level Height Siblings Path There exists only one path between any two nodes Ancestor: Any node z is ancestor of x if z lies in the path between root node and x Descedant: Nodes which are not ancestors to x are the descendant to x. Subtree: The root of subtree is usually used to name that subtree Degree Forest Definition of a tree Binary Tree An empty tree can be a binary tree Similar trees: If same struture Copies: Same struccture and same contents Properties: Max no of nodes on any level x is 2 x Max no of nodes in a tree with a heoght h is 2 h -1 The minimum number of nodes possible in a binary tree of height h is h. If a binary tree contains n nodes, then its maximum heoght possible is log 2 (n+1) Total number of nodes= total no of edges+1 Strictly Binary T...