バイナリ検索ツリーから削除したノードを返す

Question

ノードをBSTから特定の値だけ削除するメソッドを作成しようとしていますが、この削除された値を返す必要があります。私は再帰的な実装の例を見出しましたが、その性質上、削除されたノードを返すことはできません。ここで私は

public TreeNode remove(TreeNode node, int data) { 
     if (null == node) { 
      return null; 
     } 
     if (data < node.st.getkey()) { 
      node.left = remove(node.left, data); 
     } else if (data > node.st.getkey()) { 
      node.right = remove(node.right, data); 
     } else { // case for equality 

      if (node.left != null && node.right != null) { 
       TreeNode minInRightSubTree = min(node.right); 

       copyData(node , minInRightSubTree); 

       node.right = remove(node.right, minInRightSubTree.st.getkey()); 
      } else { 
       if (node.left == null && node.right == null) { 
        node = null; 
       } else {// one child case 
        TreeNode deleteNode = node; 
        node = (node.left != null) ? (node.left) : (node.right); 
        deleteNode = null; 
       } 
      } 
     } 
     return node; 
    } 

が、私はそれが削除されたノードを返す作るためにいくつかのハックを考え出すことができるか、私は繰り返しアルゴリズムになっているはずです（そして、あなたがリンクで私をフックすることができればそうならば、私はそれを本当に感謝し、今持っているものです）。

Answer 1

ルートだけでなく、ルートノードと削除ノードのペアを返すこともできます（削除されていない場合はnull）。 Map.Entryまたは新しいクラスを使用して2つのフィールドを格納できます（わかりやすいので、新しいクラスをお勧めします）。 あなたの可能な新しい署名はpublic Map.Entry<TreeNode, TreeNode> remove(TreeNode node, int data)