Question

A data structure to store trees with an arbitrary number of children at each node is: public class TreeNode / Integer data, TreeNode firstChild; TreeNode nextSibling / Write a recursive Java method to return the leaf node with minimum value given the root of the tree. All elements are unique and if there are no leaf nodes you should return null. Your method signature should be: _______

Answer 1

Answer:

TreeNode minimum(TreeNode root) {

   if (root != null) {

       if (firstChild == null && nextSibling == null) {

           return root;

       } else {

           TreeNode begin = minimum(root.firstChild);

           TreeNode last = minimum(root.nextSibling);

           if (begin == false && (last == false || begin.data < last.data)) {

               return begin;

           } else {

               return last;

           }

   } else {

       return null;

   }

}

Explanation:

The Java program defines a recursive method called minimum that calls itself twice with the first and last leaf of the treenode as the respective arguments. and returns the minimum value of the treenode if the root argument is not undefined.