CODEWITHSUNDEEP
javarecursionbinary-tree
user16655
user16655

Reputation: 1941

Find rightmost children in binary tree java

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?

Upvotes: 4

Views: 8511

Answers (5)

nem035
nem035

Reputation: 35481

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

Upvotes: 6

Trevor Freeman
Trevor Freeman

Reputation: 7232

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

Upvotes: 4

maszter
maszter

Reputation: 3720

I prefer single return statement within simple methods, so it can look like:

public Node findLastElement(Node root) {
    return root != null && root.right != null ? findLastElement(root.right) : root;
}

Upvotes: 0

Maciej Szumielewicz
Maciej Szumielewicz

Reputation: 325

Additional check on x if method is called with null argument 

public Node findLastElement(Node root) {
  Node x = root;

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

}

Upvotes: 2

Abhinav
Abhinav

Reputation: 2085

You need to check for both current node being non-null and it's right most node being non-null, this will take care of the case when the very first node passed is null too.

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

Upvotes: 0

Related Questions