Tree traversal examples for Binary Search Tree

The example of the BST and normal Binary tree traversals below
The tree on which we will execute the traversal is as follows.

We have used a stringbuffer object to get the nodes which have been traversed. This will help us if we want to print the tree in any of these 3 orders. The TreeNode class defined in previous examples have been modified to have these methods. You can check out the other examples here.

The inorder traversal method is

public static void getInorder(TreeNode node, StringBuffer buf){
	if (node==null){
		return;
	}
	getInorder(node.left, buf);
	buf.append(" "+node.value);
	getInorder(node.right, buf);
}

For preorder traversal

public static void getPreOrder(TreeNode node, StringBuffer buf){
	if (node==null){
		return;
	}
	buf.append(" "+node.value);
	
	getPreOrder(node.left, buf);
	
	getPreOrder(node.right, buf);
}

For postorder traversal the method looks like this

public static void getPostOrder(TreeNode node, StringBuffer buf){
	if (node==null){
		return;
	}		
	getPostOrder(node.left, buf);
	
	getPostOrder(node.right, buf);
	
	buf.append(" "+node.value);
}

The test code for the traversals is below

public class BSTUtil {

public static void main(String[] args) {
	TreeNode root=new TreeNode(8);
	TreeNode.insert(root, new TreeNode(3));
	TreeNode.insert(root, new TreeNode(10));
	TreeNode.insert(root, new TreeNode(6));
	TreeNode.insert(root, new TreeNode(1));
	TreeNode.insert(root, new TreeNode(14));
	TreeNode.insert(root, new TreeNode(4));
	TreeNode.insert(root, new TreeNode(7));
	TreeNode.insert(root, new TreeNode(13));
	
	StringBuffer inorderbuf=new StringBuffer();
	StringBuffer preorderbuf=new StringBuffer();
	StringBuffer postorderbuf=new StringBuffer();
	
	TreeNode.getInorder(root, inorderbuf);
	TreeNode.getPreOrder(root, preorderbuf);
	TreeNode.getPostOrder(root, postorderbuf);
	
	System.out.println("In order tree is "+inorderbuf);
	System.out.println("Pre order tree is "+preorderbuf);
	System.out.println("Post order tree is "+postorderbuf);
}
}

Output of the test code

In order tree is  1 3 4 6 7 8 10 13 14
Pre order tree is  8 3 1 6 4 7 10 14 13
Post order tree is  1 4 7 6 3 13 14 10 8

 

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself