Find rightmost children in binary tree java

Question

I'm having some trouble finding the last element (the rightmost child) in my binary tree.

This is what I have so far:

public Node findLastElement(Node root) {
  Node x = root;
  if (x != null)
      findLastElement(x.right);
  return x;
}

If I print the elements, the last one that prints is the last element, but I can't seem to "get" that element. When i try to return x after the loop, I get a nullpointer. How can I save the last element and return it?

Answer 1

You can obtain the right-most element recursively as such:

public Node findLastElement(Node root) {
    if (root == null) {
        return null;
    }
    if (root.right == null) {
        return root;
    }
    return findLastElement(root.right);
}

You can also do it iteratively. Iteration is usually better in terms of memory because it doesn't have the additional stackframes created with recursion.

public Node findLastElement(Node root) {
    if(root == null) {
        return null;
    }
    Node x = root;
    while(x.right != null) {
        x = x.right;
    }
    return x;
}

And there is not much need for a temp variable x. Since java passes reference by value, (they are a copy of original reference) any assignment we make to the input argument root is local and isn't reflected outside of the findLastElement method.

public Node findLastElement(Node root) {
    if(root == null) {
        return null;
    }
    while(root.right != null)
        root = root.right;
    return root;
}

Answer 2

You need to return the result of the recursive function call.

E.g.

public Node findLastElement(Node x) {
  if (x != null && x.right != null)
      return findLastElement(x.right);
  else
      return x;
}