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

The `traverse` method is for using the elements in your binary tree but you're returning the root left, root right or root (even if root is `null`!). The idea to recursive functions is to define the base case and then the repetitive code to get until that base case — Luiggi Mendoza, Apr 12 '12 at 03:54
What kind of a traversal are you trying to do? is it a `BST`? Do you need to insert a node in the right place in a `BST`? — noMAD, Apr 12 '12 at 03:54
If you traverse left, you return as last step in line 4, and never traverse right, and never return currentNode. That doesn't look alright. — user unknown, Apr 12 '12 at 03:59
Where are the specific values? Your function almost looks like a pre-order traversal, but as it's not clear what it's supposed to do, it's impossible to evaluate how well it achieves it. — luser droog, Apr 12 '12 at 04:00

Makoto · Accepted Answer · 2018-04-27T19:07:32.533

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

For the search example, the first recursive call should check that the result is not null and then only check the right side if it is null. Else it will only return a result if the search value is in the lower left most node. public Node traverse (Node root, int data){ if(root.data == data) { return root; } if (root.left != null){ Node val = traverse (root.left, data); if(val != null){ return val; } else if (root.right != null){ return traverse (root.right, data); } } return null; } — Aaron, Apr 27 '18 at 18:44
the algorithm in the answer will return 'null' if the data is not found somewhere in the left most branch, it will then bubble that result all the way to the top, even if the data lies somewhere else in the tree. There's no step to force it to go down the 'right' path. see this answer https://stackoverflow.com/a/5938541/572166 — Aaron, Apr 27 '18 at 19:01

score 1 · Answer 2 · answered Apr 12 '12 at 04:06

1

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.

answered Apr 12 '12 at 04:06

Amit Vig

175
2
12

1

Exactly. Draw it on paper and understand the steps first. Then insert print statements in your code so you can see what is actually happening at each step. Once you get the concept of recursion it's not really that hard. – Rick Mangi Apr 12 '12 at 04:12

score 0 · Answer 3 · answered Apr 12 '12 at 04:03

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)

Traversing a Binary Tree Recursively

3 Answers3