Tree Traversal- in, pre & post | Binary Search Tree | m-way Search Tree | Data Structure & Algorithm

TRAVERSING BINARY TREES

There are three standard ways of traversing a binary tree T with root R. These three algorithms, called preorder, inorder and postorder, are as follows: Preorder (1) Process the root R. (2) Traverse the left subtree of R in preorder. (3) Traverse the right subtree of R in preorder. Inorder (1) Traverse the left subtree of R in inorder. (2) Process the root R. (3) Traverse the right subtree of R in inorder. Postorder (1)Traverse the left subtree of R in postorder. (2)Traverse the right subtree of R in postorder. (3)Process the root R. Observe that each algorithm contains the same three steps, and that the left subtree of R is always traversed before the right subtree. The difference between the algorithms is the time at which the root R is processed. Specifically, in the "pre" algorithm, the root R is processed before the subtrees are traversed; in the "in" algorithm, the root R is processed between the traversals of the subtrees; and in the "post" algorithm, the root R is processed after the subtrees are traversed. BINARY SEARCH TREES A binary search tree, also known as an ordered binary tree, is a variant of binary trees in which the nodes are arranged in an order. In a binary search tree, all the nodes in the left sub-tree have a value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a value either equal to or greater than the root node. The same rule is applicable to every sub-tree in the tree. To summarize, a binary search tree is a binary tree with the following properties: 1. The left sub-tree of a node N contains values that are less than N’s value. 2. The right sub-tree of a node N contains values that are greater than N’s value. 3. Both the left and the right binary trees also satisfy these properties and, thus, are binary search trees. OPERATIONS ON BINARY SEARCH TREES Inserting a New Node in a Binary Search Tree The insert function is used to add a new node with a given value at the correct position in the binary search tree. Adding the node at the correct position means that the new node should not violate the properties of the binary search tree. In the algorithm, the insert function checks if the current node of TREE is NULL. If it is NULL, the algorithm simply adds the node, else it looks at the current node’s value and then recurs down the left or right sub-tree.If the current node’s value is less than that of the new node, then the right sub-tree is traversed, else the left sub-tree is traversed.The insert function continues moving down the levels of a binary tree until it reaches a leaf node. The new node is added by following the rules of the binary search trees. That is,if the new node’s value is greater than that of the parent node, the new node is inserted in the right sub-tree, else it is inserted in the left sub-tree. The insert function requires time proportional to the height of the tree in the worst case. It takes O(log n) time to execute in the average case and O(n) time in the worst case. Multi-way Search Trees We have discussed that every node in a binary search tree contains one value and two pointers,left and right, which point to the node’s left and right sub-trees, respectively.The same concept is used in an M-way search tree which has M – 1 values per node and M subtrees. In such a tree, M is called the degree of the tree. Note that in a binary search tree M = 2, so it has one value and two sub-trees. In other words, every internal node of an M-way search tree consists of pointers to M sub-trees and contains M – 1 keys, where M greater than 2.

For more detail click here