CODEWITHSUNDEEP
javarecursiontreebinary-tree
Chris
Chris

Reputation: 1

Binary Tree - How to traverse recursive without any parameters

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

Answers (1)

sverre
sverre

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

Related Questions