Nyx - 8 months ago 56

Java Question

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;

}

Answer

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;
}
```

Source (Stackoverflow)