Returning a value from a function that utilizes recursion-CodePudding

I have created a heap using a binary tree containing nodes. I have this add function that is supposed to insert/add a new node in the heap and put it in the correct position. While the add part works great, something I've been strugguling with figuring out is how you would go about having the add function return a value Depth, with depth representing how "deep" down the tree the node is added. The main issue comes from the fact that the function utilizes recursion which makes it difficult to manage a depth counter. I'm unable to "add" an int to the Node class because previous lazy coding (switching values instead of new nodes)

For example:
    System.out.println(tree.add(5)); //prints 0
    System.out.println(tree.add(2)); //prints 0
    System.out.println(tree.add(7)); //prints 0
    System.out.println(tree.add(1)); //prints 0
    System.out.println(tree.add(100)); //print 2

Code:

public class HeapBinaryTree {
    Node root;

    public class Node {
        public Integer key;
        public Node left, right;
        public int size;
        public int value;

        public Node(Integer key) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
        }
        private Integer add(Integer key) { 
            Node cur = this;
            cur.size  ;

            if (key < cur.key) {
                int temp = cur.key;
                cur.key = key;
                key = temp;
            }
            if (cur.left == null) {
                cur.left = new Node(key);
                return
            }
            if (cur.right == null) {
                cur.right = new Node(key);
                return
            }
            if (cur.left.size < cur.right.size) {
                cur.left.add(key);
            } else {
                cur.right.add(key);
            }
            return
        }
    }

        public Integer addFirst(Integer key) { //Outside node class
        if (root == null) {
            root = new Node(key);
            return 0;
        } else {
            int ret = root.depth;
            ret = root.add(key);
            return ret; //I want to return depth here
        }

How would I go about returning the "correct" depth even though the function utilizes recursion?

CodePudding user response：

Change your method to take the current depth and then return the new depth. Use an overload for the first call, which will default to depth 0. Increment when recursing.

private Integer add(Integer key) {
    return add(key, 0);
}

private Integer add(Integer key, int depth) { 
    Node cur = this;
    cur.size  ;

    if (key < cur.key) {
        int temp = cur.key;
        cur.key = key;
        key = temp;
    }
    if (cur.left == null) {
        cur.left = new Node(key);
        return depth;
    }
    if (cur.right == null) {
        cur.right = new Node(key);
        return depth;
    }
    if (cur.left.size < cur.right.size) {
        return cur.left.add(key, depth   1);
    } else {
        return cur.right.add(key, depth   1);
    }
}

CodePudding user response：

You can do this inside out: in the base case return 0, and as recursion is unwound, add 1:

        private Integer add(Integer key) { 
            Node cur = this;
            cur.size  ;

            if (key < cur.key) {
                int temp = cur.key;
                cur.key = key;
                key = temp;
            }
            if (cur.left == null) {
                cur.left = new Node(key);
                return 1; // base case
            }
            if (cur.right == null) {
                cur.right = new Node(key);
                return 1; // base case
            }
            // Make the recursive call and add 1 to its returned depth
            if (cur.left.size < cur.right.size) {
                return 1   cur.left.add(key);
            } else {
                return 1   cur.right.add(key);
            }
        }