Clever Geek Handbook

Find right children in java binary tree

I am having trouble finding the last element (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 items, the last one that prints is the last item, but I cannot "get" that item. When I try to return x after the loop, I get nullpointer. How do I keep the last item and return it?

+3


source to share


5 answers


You can get the right-most element as recursively:

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

You can also do this iteratively. Iteration is usually better from a memory standpoint because it doesn't have additional stack frames 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 no need for a temp variable x

. Since java passes the reference by value (they are a copy of the original reference), any assignment we make to the input argument root

is local and not reflected outside the method findLastElement

.

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


source


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

eg.



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


source


Additional check for x if method with zero argument

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

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

}
+2


source


You need to check that the current node is not null and it has the right most of all node to be non-empty, this will take care of the case where the first first node is passed null as well.

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


source


I prefer the single return operator in simple methods, so it might look like this:

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


source






More articles:


All Articles