We can traverse the BST in three ways
- Pre-order traversal
- In-Order traversal
- Post-order traversal.
We can easily traverse the BST using recursion.
For example pre-order traversal with recursion:
| preorder(root) { print(root->data); if(root->left) preorder(root->left); if(root->right) preorder(root->right); } |
Pre-order traversal without recursion:
| int top; struct Node *stack[100]; void preorder(root) { top=-1; it(root==NULL) return; push(root); while(top!=-1) { struct Node *node = pop(); print(node->data); if(node->right) push(node->right); if(node->left) push(node->left); } } void push(struct Node *node) { stack[++top] = node ; } struct Node* pop() { return stack[top–]; } |
For example in-order traversal with recursion:
| preorder(root) { if(root->left) preorder(root->left); print(root->data); if(root->right) preorder(root->right); } |
In-order traversal without recursion:
| void inorder(root) { take stack; while(true) { while(root not null) { push(root); root = root to left; } if(stack is empty) break; root = pop(); print(root to data); root = root to right ; } } |
Post order traversal with recursion:
| postorder(root) { if(root->left) postorder(root->left); if(root->right) postorder(root->right); print(root->data); } |
Post order traversal without recursion:
Repeat until s1 is empty:
- Take two stacks s1, s2.
- Push nodes address into s1.
- If s1 is not empty, pop() and push on to the s2.
- Find left and right child push on to the s1
- Display elements of s2 = results post order.
| postorder(node) { push node into s1 stack; while(s1 is not empty) { node = pop() from s1 push node into s2 stack; if(node -> left) push node-> left into s1 if(node -> right) push node -> right into s1 } while(s1 is not empty) { pop() and print items…. } } |