解答と解説: Lowest Common Ancestor in Binary Search Tree

「問題演習: Lowest Common Ancestor in Binary Search Tree」の解答編です。この問題は単なる二分木ではなく、二分探索木であることに注目する必要があります。それらの違いについては解説で述べたいと思います。

解答例

Javaでの解答例です。

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public Node lowestCommonAncestor(Node root, Node n1, Node n2) {
	if (n1.value < root.value && n2.value < root.value) {
	return lowestCommonAncestor(root.left, n1, n2);
	}
	if (n1.value > root.value && n2.value > root.value) {
	return lowestCommonAncestor(root.right, n1, n2);
	}
	return root;
	}
	}

view raw lca-in-bst.java hosted with ❤ by GitHub

解説

単なる二分技は子要素が最大 2 つに別れている木です。二分探索木は二分技が持つ特徴に加え、左の子要素は自身より小さく、右の子要素は自身より大きいという特徴を持っています。前回の記事で問題の入出力例を示す際に例として与えた木は、下記のように二分探索木の特徴を有しています。

      4
    /   \
   2     6

  / \   / \

 1   3 5   7

今回の問題は、2 つのノードの共通の親ノードのうち葉にもっとも近いものを探すというものでした。二分探索木の特徴を用いると、今回の問題は 3 つの場合を考慮すれば十分であることがわかります。

1. 与えられた 2 つのノードが両方とも現在のノードより小さい時、それらの共通の親で葉にもっとも近いものは、左の子要素以下に存在する。
2. 与えられた 2 つのノードが両方とも現在のノードより大きい時、それらの共通の親で葉にもっとも近いものは、右の子要素以下に存在する。
3. 与えられた 2 つのノードの片方が現在のノードより小さく、もう一方が大きい場合、現在のノードが共通の親でもっとも葉に近いノードである。

解答例に示したプログラムは、上記の 3 つの場合分けを忠実に行い、再帰を用いて葉ノードに向かって順に調べているが分かると思います。


以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。