How to find the next in order successor in a binary tree?

Question

I'm trying to implement an Iterator in my own TreeSet class. However my attempt at creating it only works until the current node is the root. The Iterator looks like this:

Constructor:

public TreeWordSetIterator()
{
    next = root;

    if(next == null)
        return;

    while(next.left != null)
        next = next.left;
}

hasNext:

public boolean hasNext()
{
    return next != null;
}

Next:

public TreeNode next()
{
    if(!hasNext()) throw new NoSuchElementException();

    TreeNode current = next;

    next = findNext(next); // find next node

    return current;
}

findNext:

private TreeNode findNext(TreeNode node)
{
    if(node.right != null)
    {
        node = node.right;

        while(node.left != null)
            node = node.left;

        return node;
    }
    else
    {
        if(node.parent == null)
            return null;

        while(node.parent != null && node.parent.left != node)
            node = node.parent;

        return node;
    }
}

This works fine up until I get to my root node. So I can only iterate through the left child of root, not the right. Can anyone give me a few tips on what I'm doing wrong? I don't expect a solution, just a few tips.

Question: How can I find the next node in a TreeSet given each node points to its parent, left-child and right-child.

Thanks in advance

Answer 1

It helps to consider the rules of a Binary Search Tree. Let's suppose the previously returned node is n:

• If n has a right subtree, then the node with the next value will be the leftmost node of the right subtree.
• If n does not have a right subtree, then the node with the next value will be the first ancestor of n that contains n in its left subtree.

Your code is correctly handling the first case, but not the second. Consider the case where node is the leftmost leaf of the tree (the starting case). node has no right child, so we go straight to the else. node has a parent, so the if-clause is skipped. node.parent.left == node, so the while clause is skipped without executing at all. The end result is that node gets returned. I'd expect your iterator to continue returning the same node forever.

Answer 2

There are 3 main ways you can iterate a binarry tree

private void inOrder(TreeNode node) {
    if(isEmpty())return;
    if(node.getLeftNode()!=null)inOrder(node.getLeftNode());
    System.out.print(node.getNodeData()+" ");
    if(node.getRightNode()!=null)inOrder(node.getRightNode());
}

private void preOrder(TreeNode node) {
    if(isEmpty())return;
    System.out.print(node.getNodeData()+" ");
    if(node.getLeftNode()!=null)preOrder(node.getLeftNode());
    if(node.getRightNode()!=null)preOrder(node.getRightNode());
}

private void postOrder(TreeNode node) {
    if(isEmpty())return;
    if(node.getLeftNode()!=null)postOrder(node.getLeftNode());
    if(node.getRightNode()!=null)postOrder(node.getRightNode());
    System.out.print(node.getNodeData()+" ");
}

//use
inOrder(root);
preOrder(root);
postOrder(root);

Its simple as that ,your code doesn't really makes sense to me, is there something else you are trying to do besides iterating in one of this ways?

Answer 3

I think you need to save previous point in your iterator so you know where you've been before

Here some code but be aware that it is not complete you should do it by yourself and it's just to show you the idea. it also doesn't handle the root node.

findNext(TreeNode node, TreeNode previousNode) {

  if(node.left != null && node.left != previousNode && node.right != previousNode){ //go left if not been there yet
    return node.left; 
  }
  if(node.right != null && node.right != previousNode){ //go right if not been there yet
    return node.right;
  }
  return findNext(node.parent, node); //go up and pass current node to avoid going down
}

Answer 4

A good approach is to use a stack to manage sequencing, which is sort of done for you if you use a recursive traversal (instead of trying to build an Iterator at all) as described in SteveL's answer.

As you want to start from the left, you first load onto the stack the root node and its leftmost children in the proper order (push while going down to the left from the root).

Always pop the next from the top of the stack, and push its right child (if any) and all its leftmost children before returning the one you just popped, so that they're next in line.

By this approach, the top of the stack will always be the next to return, and when the stack is empty, there's no more...

In code:

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

public class TreeNodeInOrderIterator<T> implements Iterator<T> {

    private final Stack<TreeNode<T>> stack;

    public TreeNodeInOrderIterator(TreeNode<T> root) {
        this.stack = new Stack<TreeNode<T>>();
        pushLeftChildren(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public T next() {
        if (!hasNext())
            throw new NoSuchElementException();
        TreeNode<T> top = stack.pop();
        pushLeftChildren(top.right);
        return top.val;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    private void pushLeftChildren(TreeNode<T> cur) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

}

In this code, TreeNode is defined by

public class TreeNode<T> {
    T val;
    TreeNode<T> left;
    TreeNode<T> right;
    TreeNode(T x) { val = x; }
}

If you want to have each node also know its parent, that's ok, but all the traversal is by using what's on the stack and adding to the stack using the left and right child links.