Reputation: 1
I don't know how to traverse a given binary tree recursively, just by using the following methodes of the tree. For example every TreeNode has an int Value and a getter TreeNode.getValue() and now i want to find the node with the maximum value in the tree. Note that a tree has only a pointer to its currentNode and u can move to the parent, right, left or root node.
My Question:
Tree tree;
public int findMaxValue() {
//how to implement this as recursive function
}
The tree class:
/**
* The abstract class for a tree.
* @author JK, KM
*/
public abstract class Tree {
/**
* Moves to the left child of the current node
*
* @return true if left child exists and the move was successful; otherwise
* false
*/
public abstract boolean moveToLeftNode();
/**
* Moves to the right child of the current node
*
* @return true if right child exists and the move was successful; otherwise
* false
*/
public abstract boolean moveToRightNode();
/**
* Moves to the parent of the current node
*
* @return true if parent exists and the move was successful; otherwise
* false
*/
public abstract boolean moveToParentNode();
/**
* @return true if left child exists; otherwise false
*/
public abstract boolean hasLeftNode();
/**
* @return true if right child exists; otherwise false
*/
public abstract boolean hasRightNode();
/**
* @return true if parent exists; otherwise false
*/
public abstract boolean hasParentNode();
/**
* Sets the left child of the current node
*
* @return true if successful; otherwise false (no root set)
*
*/
public abstract boolean setLeftNode(TreeNode node);
/**
* Sets the right child of the current node
*
* @return true if successful; otherwise false (no root set)
*
*/
public abstract boolean setRightNode(TreeNode node);
/**
* Sets the current node. If the tree is empty, sets the root.
*
*/
public abstract void setCurrentNode(TreeNode node);
/**
* @return the current node or null if the tree is empty
*/
public abstract TreeNode getCurrentNode();
/**
* moves to the root node of this tree
*
* @return true if there's a root; otherwise false
*/
public abstract boolean moveToRoot();
/**
* clears the whole tree, which includes deleting all nodes and the root
* node
*/
public abstract void clearTree();
Upvotes: 0
Views: 2770
Reputation: 6919
You can traverse a binary tree recursively like this:
public int findMaxValue() {
return max(this.node.getValue(),
this.getLeftChild().findMaxValue(),
this.getRightChild().findMaxValue());
}
Implementing this given your Tree
interface and checking for leaf nodes is left as an exercise.
Upvotes: 2