In this tutorial we will learn about Binary Search Tree Traversal with examples. We have a Binary Search Tree which is following.
Binary Search Tree Traversal Methods
There are various methods to traverse the binary search tree. Following are the basic methods used to Traverse the Binary Search Tree.
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
1. Inorder Traversal
Explanation:
- Traverse the left subtree.
- Visit the root node.
- Traverse the right subtree.
Recursion is the best and simple way to traverse over the binary search tree. Everything you should know about the Recursion to traverse the BST in best way.
Code
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary search tree
public static Node createBST(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = createBST(root.left, val);
} else {
root.right = createBST(root.right, val);
}
return root;
}
// traverse the bst inorder
static void inorder(Node root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
public static void main(String[] args) {
int[] values = {12, 8, 10, 1, 3, 4, 6, 9, 15};
Node root = null;
for(int i=0; i<values.length; i++){
root = createBST(root, values[i]);
}
// traverse over the bst
inorder(root);
System.out.println("");
}
}
Answer: 1 3 4 6 8 9 10 12 15
2. Preorder Traversal of Binary Search Tree
Explanation:
- Visit the root.
- Traverse the left subtree.
- Traverse the right subtree.
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary search tree
public static Node createBST(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = createBST(root.left, val);
} else {
root.right = createBST(root.right, val);
}
return root;
}
// traverse the bst preorder
static void preorder(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
public static void main(String[] args) {
int[] values = {12, 8, 10, 1, 3, 4, 6, 9, 15};
Node root = null;
for(int i=0; i<values.length; i++){
root = createBST(root, values[i]);
}
// traverse over the bst
preorder(root);
System.out.println("");
}
}
Answer: 12 8 1 3 4 6 10 9 15
3. Postorder Traversal of BST
Explanation:
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root node.
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary search tree
public static Node createBST(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = createBST(root.left, val);
} else {
root.right = createBST(root.right, val);
}
return root;
}
// traverse the bst postorder
static void postorder(Node root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
int[] values = {12, 8, 10, 1, 3, 4, 6, 9, 15};
Node root = null;
for(int i=0; i<values.length; i++){
root = createBST(root, values[i]);
}
// traverse over the bst
postorder(root);
System.out.println("");
}
}
Answer: 6 4 3 1 9 10 8 15 12
Thank you for reaching out this tutorial. You can comment in the comments section below for any doubt or query. If you like this tutorial please comment.
Free Blog post
You can post your content here Free.
Learn more about BST Traversal.
