How do I call one function in another function?

Question

I created functions that are able to get the successor Node in a binary search tree traversing it in all 3 ways, in order, post order, and pre order. My challenge now is try to put them all in a getNextItem method, and call each of those aforementioned functions using the getNextItem method. I know what the skeleton of the getNextItem method should be I just don't know how to complete it. I also included the insert and main method if anyone wanted to test my functions. Please note I cannot change the parameters in the getNextItem method.

public class BinaryTree {
    public static final int INORDER = 1;
    public static final int PREORDER = 2;
    public static final int POSTORDER = 3;
    TreeNode root;
    TreeNode currentNode;

    class TreeNode {
        int data;
        TreeNode left, right, parent, root;

        TreeNode(int data) {
            this.data = data;
            left = right = parent = root = null;
        }
    }

    TreeNode insert(TreeNode node, int data) {
        if (node == null) {
            return (new TreeNode(data));
        }
        else {
            TreeNode temp = null;

            if (data <= node.data) {
                temp = insert(node.left, data);
                node.left = temp;
                temp.parent = node;
            }
            else {
                temp = insert(node.right, data);
                node.right = temp;
                temp.parent = node;
            }

            return node;
        }
    }

    public Comparable getNextItem(int orderType) {
        switch (orderType) {
            case INORDER:
                break;
            case PREORDER:
                break;
            case POSTORDER:
                break;
        return;
    }

    TreeNode inOrderSuccessor(TreeNode n) {
        if (n.right != null) {
            return minValue(n.right);
        }

        TreeNode p = n.parent;
        while (p != null && n == p.right) {
            n = p;
            p = p.parent;
        }
        return p;
    }

    TreeNode minValue(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    TreeNode preorderSuccessor(TreeNode n) {
        if (n.left != null)
            return n.left;

        if (n.right != null)
            return n.right;

        TreeNode curr = n, parent = curr.parent;
        while (parent != null && parent.right == curr) {
            curr = curr.parent;
            parent = parent.parent;
        }

        if (parent == null)
            return null;

        return parent.right;
    }

    TreeNode postorderSuccessor(TreeNode n) {
        if (n == null)
            return null;

        TreeNode parent = n.parent;
        if (parent.right == null || parent.right == n)
            return parent;

        TreeNode curr = parent.right;
        while (curr.left != null)
            curr = curr.left;

        return curr;
    }


    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        TreeNode root = null, temp = null, suc = null, suc2 = null, suc3 = null, min = null;
        root = tree.insert(root, 20);
        root = tree.insert(root, 8);
        root = tree.insert(root, 22);
        root = tree.insert(root, 4);
        root = tree.insert(root, 12);
        root = tree.insert(root, 10);
        root = tree.insert(root, 14);
        temp = root.left.right.right;
        suc = tree.inOrderSuccessor(temp);
        System.out.println(
                "Inorder successor of "
                        + temp.data + " is " + suc.data);
        suc = tree.preorderSuccessor(temp);
        System.out.println(
                "Preorder successor of "
                        + temp.data + " is " + suc.data);
        suc = tree.postorderSuccessor(temp);
        System.out.println(
                "Postorder successor of "
                        + temp.data + " is " + suc.data);

    }
}

Answer 1

I would suggest starting with currentNode = null, so that the very first call of getNextItem will actually return the data of the very first node in the given traversal order.

I would also have the class manage its root member itself, so that the main program does not have to update it after calling insert.

The name minValue is not really representative of what it does, as it does not return a node's value, but a node. It could be a method on the TreeNode class.

Here is how it could look:

class BinaryTree {
    public static final int INORDER = 1;
    public static final int PREORDER = 2;
    public static final int POSTORDER = 3;
    TreeNode root, currentNode;

    public class TreeNode {
        int data;
        TreeNode left, right, parent;

        public TreeNode(int data) {
            this.data = data;
            left = right = parent = null; // There should be no root here.
        }
            
        TreeNode minNode() {
            return left == null ? this : left.minNode();
        }
    }

    public BinaryTree() {
        root = null;
    }
 
    public void insert(int newData) {
        root = root == null ? new TreeNode(newData) : insert(root, newData);
    }
    
    private TreeNode insert(TreeNode node, int newData) {
        if (node == null) return new TreeNode(newData);
        if (newData < node.data) {
            node.left = insert(node.left, newData);
            node.left.parent = node;
        } else if (newData > node.data) { 
            node.right = insert(node.right, newData);
            node.right.parent = node;
        }
        return node;
    }

    private TreeNode inOrderSuccessor(TreeNode node) {
        if (node == null) return root.minNode();
        if (node.right != null) return node.right.minNode();
        while (node.parent != null) {
            if (node == node.parent.left) return node.parent;
            node = node.parent;
        }
        return null;
    }
    
    private TreeNode preOrderSuccessor(TreeNode node) {
        if (node == null) return root;
        if (node.left != null) return node.left;
        if (node.right != null) return node.right;
        while (node.parent != null) {
            if (node == node.parent.left && node.parent.right != null) {
                return node.parent.right;
            }
            node = node.parent;
        }
        return null;
    }
    
    private TreeNode postOrderSuccessor(TreeNode node) {
        if (node == null) return root.minNode();
        if (node.parent == null) return null;
        if (node.parent.right == node || node.parent.right == null) return node.parent;
        node = node.parent.right;
        while (node.left == null && node.right != null) {
            node = node.right;
        }
        return node.minNode();
    }
    

    public Comparable getNextItem(int orderType) {
        if (root == null) return null;
        switch (orderType) {
            case INORDER:
                currentNode = inOrderSuccessor(currentNode);
                break;
            case PREORDER:
                currentNode = preOrderSuccessor(currentNode);
                break;
            case POSTORDER:
                currentNode = postOrderSuccessor(currentNode);
                break;
        }
        return currentNode == null ? null : currentNode.data;
    }
    
    public void reset() {
        currentNode = null;
    }

    void print() {
        print(root, "");
    }

    void print(TreeNode node, String tab) {
        if (node == null) return;
        print(node.right, tab + "  ");
        System.out.println(tab + node.data);
        print(node.left, tab + "  ");
    }

    public static void main(String[] args) {
        Main tree = new BinaryTree();
        tree.insert(8);
        tree.insert(3);
        tree.insert(10);
        tree.insert(9);
        tree.insert(1);
        tree.insert(6);
        tree.insert(7);
        tree.print();
        tree.reset();
        System.out.println("In-order traversal:");
        while (true) {
            Comparable data = tree.getNextItem(INORDER);
            if (data == null) break;
            System.out.print(data + " ");
        }
        System.out.println();

        tree.reset();
        System.out.println("Pre-order traversal:");
        while (true) {
            Comparable data = tree.getNextItem(PREORDER);
            if (data == null) break;
            System.out.print(data + " ");
        }
        System.out.println();

        tree.reset();
        System.out.println("Post-order traversal:");
        while (true) {
            Comparable  data = tree.getNextItem(POSTORDER);
            if (data == null) break;
            System.out.print(data + " ");
        }
        System.out.println();
    }
}

Answer 2

First of all, I think your *successor methods need to be recursive; otherwise you won't get the correct successor according to the ordering method. Assuming that you have done that:

The getNextItem implies that you keep a cursor (e.g. a current node to traverse on), or you provide a currentNode as a parameter. If you don't want an iterative behavior (e.g. if you don't want a cursor), then the second option would be better for you; which is to provide a currentNode as a parameter, and then select the appropriate method WRT the order type).

   //..previous code
   public Comparable getNextItem(int orderType, TreeNode currentNode) {
        TreeNode successor = null;
        switch (orderType) {
            case INORDER:
                successor = inOrderSuccessor(currentNode);
                break;
            case PREORDER:
                successor = preOrderSuccessor(currentNode);
                break;
            case POSTORDER:
                successor = postOrderSuccessor(currentNode);
                break;
         } //end of switch
         
         return successor.data;
    }
   //..the rest

Please be aware of null checks and so on.

EDIT: If you aren't allowed to change the parameters of the getNextItem method, then your tree needs to behave as an iterator, hence you need a cursor. Since you already have a field called currentNode, then you can use that as a cursor, initially setting it to root.

Then it should look like this:

   //..previous code
   public Comparable getNextItem(int orderType) {
        TreeNode successor = null;
        switch (orderType) {
            case INORDER:
                successor = inOrderSuccessor(this.currentNode);
                break;
            case PREORDER:
                successor = preOrderSuccessor(this.currentNode);
                break;
            case POSTORDER:
                successor = postOrderSuccessor(this.currentNode);
                break;
         } //end of switch
         //keep the cursor up to date.
         this.currentNode = successor;
         return successor.data;
    }
   //..the rest

For this option to work properly, you also need to have a reset method which sets the currentNode to root, as well as keeping an eye on null values.

I would suggest a few refactors as well, like to encapsulate node management in the binary tree and make sure that your order algorithms work correctly.