Binary Search Trees are recursively defined, which makes traversal a lot much easier. There are four major types of traversals :
1. Inorder
2. Postorder
3. Preorder
4. Levelorder
Inorder Traversal
In inorder traversal, the node's left child is visited first, then the node, and then it's right child.
Inorder traversal of the above tree would give : 4, 5, 6, 7, 10, 12, 15, 20
Here's the code for inorder traversal in a tree :
Postorder Traversal
In postorder traversal, the node's left child is visited first, then it's right child, and finally the node is visited.
The postorder traversal of the above tree would give : 5, 4, 7, 6, 12, 20, 15, 10
Here's the code for postorder traversal :
Preorder Traversal
In preorder traversal, the node is visited first, then it's left child, followed by it's right child.
The preorder traversal of the above tree would give : 10, 6, 4, 5, 7, 15, 12, 20
Here's the code for preorder traversal in a tree :
Levelorder Traversal
Levelorder traversal is easiest to visualise but a little difficult to code (as compared to other traversals). In levelorder, the nodes on each level are visited one-by-one from left to right.
The level order traversal of the above tree would give : 10, 6, 15, 4, 7, 12, 20, 5
Here's the code for level ordering :
Related links :
