How to Traverse Binary Trees in Java
Binary trees are complex data structures used in computer programs to store data in memory using a common storage algorithm. By using this type of algorithm, data can be stored in a stable pattern, making retrieving and searching through data easier. Java programmers who are designing binary trees are more than likely also designing algorithms to traverse those data structures. There are three ways to traverse binary trees: in-order, pre-order, and post-order.
Other People Are Reading
Instructions
-
-
1
Traverse the binary tree using in-order traversal. Assuming that the class "BT" represents a binary tree, the following code shows how to print the tree in-order. Each node has a left and right pointer that points to the left and right nodes of the current node, along with a data item that represents its value. The in-order traversal will traverse the left node first until hitting null, and the print the parent node before traversing right and starting over. The means that any node will only print if all of its left-side child nodes have printed first:
public class BT{
public void inOrder(Node x){
if (x == null){
return; //stops recursion when there is no Node
}inOrder(x.left); //always traverse left first
print x.data; //print the data once the left node returns
inOrder(x.right); //traverse right
} -
2
Traverse the tree in pre-order. This order is similar to in-order, except that printing of the node comes before any traversal. So, the node will print its value, and then traverse left. Then, when the recursion returns to the node after traversing left, the node will then traverse right. This means that the node will always print itself before any child nodes print:
public void preOrder(Node x){
if (x == null){
return; //stops recursion when there is no Node
}print x.data; //print
inOrder(x.left); //traverse left
inOrder(x.right); //traverse right
} -
-
3
Traverse the tree post-order. This is the opposite of the pre-order traversal. A node will always look to its left or right Nodes before printing itself, meaning that all other child nodes below it will print first:
public void postOrder(Node x){
if (x == null){
return; //stops recursion when there is no Node
}inOrder(x.left); //traverse left
inOrder(x.right); //traverse right
print x.data; //print
}
-
1
