Traversing a Binary Tree Recursively

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 1

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 && data < root.data) {
        return traverse (root.left, data);
    }
    if (root.right != null && data > root.data) {
        return traverse (root.right, data);
    }
    return null;
}

Answer 2

It seems like you are traversing in the preorder methodology, but i am a little skeptical as to what exactly you wish to accomplish without actually comparing your current node with some base value that defines u have reached ur destination. I would suggest drawing out a simple tree and visualizing the steps. Then try to put that into code.

Answer 3

A recursive function returns the value of itself with a modified parameter, or a termination (exit) condition. eg, Factorial:

int factorial( int param ) {
   if ( param > 1 ) {
      return param * factorial( param -1 );
   } else {
      return 1;
   }
}

In your code, you call a 'traverse' but then do nothing with the result... When your recursive function ends, your final return will be first left child if it exists, else the first right child if it exists, else the root node.

Please give more detail as to why you need to traverse the tree (also, not sure what you meant by "copy the function and modify it in every other function", the whole idea of a function is to code-once-call-many)