Nyx - 1 year ago 87
Java Question

# Traversing a Binary Tree Recursively

I am hopelessly lost when it comes to recursive functions. I am required to create a recursive function to traverse a binary tree and insert a new node in between specific values. Would i need to recopy my traverse function and modify it in every other function that i use it in? Would someone please evaluate the traverse function?

I think my traversing code is alright.

``````Node traverse (Node currentNode){
if (!currentNode.left.equals(null)){
traverse (currentNode.left);
return currentNode.left;
}
if (!currentNode.right.equals(null)){
traverse (currentNode.right);
return currentNode.right;
}
return currentNode;
}
``````

When it comes to binary trees, there are several different types of traversals that can be done recursively. They're written in the order they're referenced then visited (L=Left child, V = visit that node, R = right child).

• In-order traversal (LVR)
• Reverse order traversal (RVL)
• Preorder traversal (VLR)
• Postorder traversal (LRV)

Your code appears to be performing the postorder traversal method, but you're getting a few things mixed up. First, the node is what you want to traverse; the data is what you want to visit. Second, you have no reason to return the node itself, in the way that this is implemented. Your code doesn't allow for a condition to say, 'I'm looking for this particular data, do you have it Mr. Node@0xdeadbeef?', which would be found with some sort of extra search parameter.

An academic BST traversal only prints the nodes itself. If you wanted to add a search functionality, it's only one more parameter, as well as an additional check for the right node.

Here's a snippet:

``````// Academic

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
if (root.left != null){
traverse (root.left);
}
System.out.println(root.data);
if (root.right != null){
traverse (root.right);
}
}

// Search with a valid node returned, assuming int

public Node traverse (Node root, int data){ // What data are you looking for again?
if(root.data == data) {
return root;
}
if (root.left != null){
return traverse (root.left, data);
}
if (root.right != null){
return traverse (root.right, data);
}
return null;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download