Binary trees, returning the next node in a preorder traversal

Question

I have an assignment and I need some help with a method.

So I have a tree like this:

                A
              /   \
             B     C
           /   \ /   \
          D    E F     G
        /   \
       H      I
     /   \
   J       K

and my method is:

public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {       

    prev = t;

    if(t.getLeft() != null) {
        preorderNext(t.getLeft(), v, prev);
    }

    if(t.getRight() != null) {
        preorderNext(t.getRight(), v, prev);
    }


    if(prev == v) {
        return t;
    }

    return null;
}

The lecturer had given a simple implementation of the tree. The class is called BinaryTree and if you want to make a node link to it then you specify what the right and left child BinaryTree node are.

A node has two links (one to the left and the other to the right child) and there is no link to the head.

So with the current method I am able to successful do a preorder traversal, I tested by writing the print statements of what the element stored at the node is.

But when I run the tests, it tells me that the next preorder node from A is B, and the next preorder node from K throws a null exception but it should be I?

Any ideas of where I am going wrong? The variable prev should hold a reference to the last node visited so if it equals to node v (which is the node I specify, to return the node after v), shouldn't I get the next node?

Answer 1

Here is an implementation of how a preorder traversal is done recursively.

public void preOrderTraversal(BinaryTree root){
    if(root == null) return;

    System.out.println(root);
    preOrderTraversal(root.getLeft());
    preOrderTraversal(root.getRight());
}

Notes:

1. I am not sure of your approach; why are you returning a node? In any case, when the root is null with that approach you can return an "emptyNode" and deal with it by an if statement.
2. As you can see I am only dealing with the root, with any level the root changes. Try to visualize this with a run-through and you will understand this concept.
3. You are missing a check for null nodes at the beginning (especially for t).

You can continue to adapt your results to this.

A final note is for the run-time complexity of this approach, I'd highly recommend understanding run-time complexities for recursive functions. It will help you a lot in the future. Check this wikipedia article for recurrence relations.

Answer 2

I am not sure if doing that task recursively is that easy.

Solving the task the iterative way using a stack could be a much better approach:

public BinaryTree preOrderNext(BinaryTree toSearch) {

    Stack<BinaryTree> openList = new Stack<BinaryTree>();

    openList.push(root);

    while (openList.empty() == false) {
        BinaryTree curr = openList.pop();

        if (curr.getRight() != null)
            openList.push(curr.getRight());

        if (curr.getLeft() != null)
            openList.push(curr.getLeft());

        if (curr.equals(toSearch) && openList.empty() == false){
            return openList.pop();
        }
    }
    return null;
}

This method is not tested, but should be working.

Answer 3

I provide an answer that runs in O(h) running time.

class Node {
    public int key;
    public Node l;
    public Node r;
    public Node p;

    public Node(int key) {
        this.key = key;
        this.l = null;
        this.r = null;
        this.p = null;
    }
}

public Node preorderNext(Node v) {
    if (v.l != null) {
        return v.l;
    } else if (v.r != null) {
        return v.r;
    } else {
        while (v.p != null) {
            if (v == v.p.l) {
                if (v.p.r != null) {
                    return v.p.r;
                } else {
                    v = v.p;
                }
            } else {
                if (v.p.p == null) {
                    return null;
                } else if (v.p == v.p.p.l) {
                    if (v.p.p.r != null) {
                        return v.p.p.r;
                    } else {
                        v = v.p;
                    }
                } else {
                    v = v.p;
                }
            }
        }
        return null;
    }
}