Find pairs in binary search tree in which sum of nodes keys is equal key

Question

There is a task:

Given a binary search tree of \$n\$ nodes, find all the pair of nodes whose sum is equal to a given number \$k\$ in \$O(n)\$ time and constant space.

Please let me know if you find bugs on any data set.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    static class Node
    {
        Node(Node left, Node right, Node parent, int key)
        {
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.key = key;
        }

        public Node left;
        public Node right;
        public Node parent;

        public int key;
    }

    public static void inOrder (Node node)
    {
        if(node.left != null) inOrder(node.left);
        System.out.println(node.key);
        if(node.right != null) inOrder(node.right);
    }

    public static Node successor (Node node)
    {
        Node successor = null;
        if(node.right != null)
        {
            node = node.right;
            while(node.left != null)
            {
                node = node.left;
            }
            successor = node;
        }
        else if(node.parent != null && node.parent.left == node) successor = node.parent;
        else if(node.parent != null && node.parent.right == node)
        {
            while(node.parent != null && node.parent.right == node)
            {
                node = node.parent;
            }
            successor = node.parent;
        }
        return successor;
    }

    public static Node predeccessor(Node node)
    {
        Node predecessor = null;
        if(node.left != null)
        {
            node = node.left;
            while(node.right != null)
            {
                node = node.right;
            }
            predecessor = node;
        }
        else if(node.parent != null && node.parent.right == node) predecessor = node.parent;
        else if(node.parent != null && node.parent.left == node)
        {
            while(node.parent != null && node.parent.left == node)
            {
                node = node.parent;
            }
            predecessor = node.parent;
        }

        return predecessor;
    }

    public static Node min (Node node)
    {
        while(node.left != null) node = node.left;
        return node;
    }

    public static Node max (Node node)
    {
        while(node.right != null) node = node.right;
        return node;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Node root = new Node(null, null, null, 5);//      5
        Node a = new Node(null, null, null, 2);   //     / \
        Node b = new Node(null, null, null, 1);   //    2   8
        Node c = new Node(null, null, null, 3);   //   /\    \
        Node d = new Node(null, null, null, 8);   //  1  3    9
        Node e = new Node(null, null, null, 9);   //

        root.left = a;
        root.right = d;
        a.parent = root;
        d.parent = root;

        a.left = b;
        a.right = c;
        b.parent = a;
        c.parent = a;

        d.right = e;
        e.parent = d;

        int sum = 10;

        //find pairs in Binary Search Tree in which sum of nodes keys is equal 10

        Node minnode = min(root);
        Node maxnode = max(root);
        while(minnode.key <= maxnode.key && minnode != maxnode)
        {
            if (minnode.key + maxnode.key == sum)
            {
                System.out.println("Pair found: " + minnode.key + " " + maxnode.key);
                minnode = successor(minnode);
                maxnode = predeccessor(maxnode);
            }
            else if(minnode.key + maxnode.key < sum)
            {
                minnode = successor(minnode);
            }
            else
            {
                maxnode = predeccessor(maxnode);
            }
        }
    }
}

Answer 1

I just have minor nitpicks.

1

You can simplify the methods for computing a successor/predecessor:

public static Node successor(Node node) {
    if (node.right != null) {
        return min(node.right);
    }

    while (node.parent != null && node.parent.right == node) {
        node = node.parent;
    }

    return node.parent;
}

Also, you compute the min(node.right) above in code; hence, you repeated yourself.

2

I would rip off the implementation of your sum pair algorithm out of main().

3

I would have a class, say, NodePair, which simply stores a pair of nodes.

4

The actual algorithm could just return the list of those NodePair objects.

5

Since you are printing the results, you could override toString() in NodePair and make it return a string in the format that meets your needs.

6

inOrder is not used. In case you don't need it either, consider removing it.

7

You import java.lang, yet you don't need to: it is imported by default. Also, you left hanging around two packages (java.util and java.io), remove them. Finally, I would encourage avoiding wildcard imports: import on individual basis, let people see what classes you use in your source.

Summa summarum

All in all, I had this in mind:

import java.util.ArrayList;
import java.util.List;

class Main {

    static class Node {

        Node(Node left, Node right, Node parent, int key) {
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.key = key;
        }

        public Node left;
        public Node right;
        public Node parent;

        public int key;

        @Override
        public String toString() {
            return new StringBuilder("Node ").append(key).toString();
        }
    }

    public static Node successor(Node node) {
        if (node.right != null) {
            return min(node.right);
        }

        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }

        return node.parent;
    }

    public static Node predeccessor(Node node) {
        if (node.left != null) {
            return max(node.left);
        }

        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }

        return node.parent;
    }

    public static Node min(Node node) {
        while (node.left != null) {
            node = node.left;
        }

        return node;
    }

    public static Node max(Node node) {
        while (node.right != null) {
            node = node.right;
        }

        return node;
    }

    public static final class NodePair {
        public Node node1;
        public Node node2;

        public NodePair(Node node1, Node node2) {
            this.node1 = node1;
            this.node2 = node2;
        }

        @Override
        public String toString() {
            return new StringBuilder("[").append(node1)
                                         .append(", ")
                                         .append(node2)
                                         .append("]")
                                         .toString();
        }
    }

    public static List<NodePair> findPairsWithSum(Node root, int sum) {
        List<NodePair> nodePairList = new ArrayList<>();
        Node minnode = min(root);
        Node maxnode = max(root);

        while (minnode.key <= maxnode.key && minnode != maxnode) {
            if (minnode.key + maxnode.key == sum) {
                nodePairList.add(new NodePair(minnode, maxnode));
                minnode = successor(minnode);
                maxnode = predeccessor(maxnode);
            } else if (minnode.key + maxnode.key < sum) {
                minnode = successor(minnode);
            } else {
                maxnode = predeccessor(maxnode);
            }
        }

        return nodePairList;
    }

    public static void main(String[] args) throws java.lang.Exception {
        Node root = new Node(null, null, null, 5);//      5
        Node a = new Node(null, null, null, 2);   //     / \
        Node b = new Node(null, null, null, 1);   //    2   8
        Node c = new Node(null, null, null, 3);   //   /\    \
        Node d = new Node(null, null, null, 8);   //  1  3    9
        Node e = new Node(null, null, null, 9);   //

        root.left = a;
        root.right = d;
        a.parent = root;
        d.parent = root;

        a.left = b;
        a.right = c;
        b.parent = a;
        c.parent = a;

        d.right = e;
        e.parent = d;

        // Print all the node pairs summing to 10.
        for (NodePair pair : findPairsWithSum(root, 10)) {
            System.out.println(pair);
        }
    }
}

Hope that helps.

Edit

Actually, what comes to printing the node pairs, I realized that it makes sense to override Node.toString() as well. After that, building a string representation of a NodePair simplifies a bit. Please, for details refer to Node.toString and NodePair.toString.