Question

Java eclipse question.

Given a binary search tree

-------------M

---------G ---------N

------D----- H

---B----F

How would you find the farthest from the root and most right side of the node?

So, in this case, farthest nodes are B and F with height of 4

But the most right side of the node is F

Therefore answer is F.

I have

//Will call helper method.

public T findRightmostLowest(){

int lv = height();//This is the maxium height of the tree(4 in this case).

   return findRightmostLowest(root, 1, lv);

}

private T findRightmostLowest(Node node, int currLv, int maxLv){

}

I appreciate your time.

Answer 1

Find farthest nodes:

To find shortest nodes we traverse binary tree with DFS and push all nodes with max depth into vector.
Code:

private void findFarthestNodes(Node node, int depth, int maxDepth, Vector<Node> list) {
  if(node == NULL) {
  return;
}

DFS(node->left, depth+1, maxDepth, list);

DFS(node->right, depth+1, maxDepth, list);

if(depth == maxDepth)
list.add(node);​​​​​

}

Find right most node:

To find right most node we just have to move from node to it's right node while it exists.
Code:

private Node findRightmostNodes(Node node) {
  if(node == NULL) {
  return NULL;
}

while(node->right != NULL)
node = node->right

}

Comment down for any queries

Please give a thumb up