How to Do Preorder Traversal in Binary Tree in Java

To do a "traversal" of a binary tree in Java means to do an algorithmic processing of the nodes in some sort of order. A "preorder" traversal means that the root node is processed first, and then the rest of the tree's nodes are processed recursively. The traversal function will simply print each node it visits to the console.

Instructions

1. Create a simple binary search tree class that has a basic constructor which initializes the node's value. Also included should be an insert method to traverse a tree and create a new node in the correct place.
   ""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;

public BinaryTree(int v) {
value = v;
}

// Insert a value into the tree
public void insert(int v) {
if(v < value) {
if(left == null)
left = new BinaryTree(v);
else
left.insert(v);
}

else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}
}""

2. Construct the root node of the binary tree, assigning it a value that's near the mean of the of the objects you'll be storing. This will ensure efficiency, since your binary tree needs to be fairly well balanced. If you're storing a distribution of numbers from 1 to 100, for example, 50 is a good value for the root node. ""BinaryTree b = new BinaryTree(50);""

3. Insert nodes into the tree in a particular order. The binary tree is not auto-balancing, so inserting nodes in a specific order helps to retain the balance. Here the nodes are place to make a short and efficiently balanced tree.""b.insert(20);
b.insert(40);
b.insert(10);
b.insert(5);
b.insert(45);

b.insert(70);
b.insert(60);
b.insert(80);
b.insert(55);
b.insert(85);""

4. Do a preorder traversal by traversing the the root node first, then the left tree and finally the right tree. It's easy to do this recursively with a small binary tree, as it doesn't overflow the stack. If your binary tree is very large, the traversal function should be implemented iteratively.

5. Add a new method, preorder, to the BinaryTree class. Here the method only prints the value of each node it visits.""public void preorder() {
System.out.println(value);
if(left != null) left.preorder();
if(right != null) right.preorder();
}""

6. Call the new method after your inserts to print the nodes in preorder.""b.preorder();"

Tips & Warnings

• In its default libraries, Java doesn't provide a binary tree class, but, as shown, it's simple enough to create a basic binary tree class.