Skip to content

Instantly share code, notes, and snippets.

@kbendick
Last active March 8, 2016 20:56
Show Gist options
  • Save kbendick/dcece90523831f90cc8f to your computer and use it in GitHub Desktop.
Save kbendick/dcece90523831f90cc8f to your computer and use it in GitHub Desktop.
finding lowest common ancestor in a binary tree
// Taken from CtCI-6th-Edition from @careercup
public class bt_lca {
/* One node of a binary tree. The data element stored is a single
* character.
*/
public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
private int size = 0;
public TreeNode(int d) {
data = d;
size = 1;
}
private void setLeftChild(TreeNode left) {
this.left = left;
if (left != null) {
left.parent = this;
}
}
private void setRightChild(TreeNode right) {
this.right = right;
if (right != null) {
right.parent = this;
}
}
public void insertInOrder(int d) {
if (d <= data) {
if (left == null) {
setLeftChild(new TreeNode(d));
} else {
left.insertInOrder(d);
}
} else {
if (right == null) {
setRightChild(new TreeNode(d));
} else {
right.insertInOrder(d);
}
}
size++;
}
public int size() {
return size;
}
public boolean isBST() {
if (left != null) {
if (data < left.data || !left.isBST()) {
return false;
}
}
if (right != null) {
if (data >= right.data || !right.isBST()) {
return false;
}
}
return true;
}
public int height() {
int leftHeight = left != null ? left.height() : 0;
int rightHeight = right != null ? right.height() : 0;
return 1 + Math.max(leftHeight, rightHeight);
}
public TreeNode find(int d) {
if (d == data) {
return this;
} else if (d <= data) {
return left != null ? left.find(d) : null;
} else if (d > data) {
return right != null ? right.find(d) : null;
}
return null;
}
private static TreeNode createMinimalBST(int arr[], int start, int end){
if (end < start) {
return null;
}
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
n.setLeftChild(createMinimalBST(arr, start, mid - 1));
n.setRightChild(createMinimalBST(arr, mid + 1, end));
return n;
}
public static TreeNode createMinimalBST(int array[]) {
return createMinimalBST(array, 0, array.length - 1);
}
public void print() {
BTreePrinter.printNode(this);
}
}
public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (!covers(root, p) || !covers(root, q)) { // Error check - one node is not in tree
return null;
}
return ancestorHelper(root, p, q);
}
public static TreeNode ancestorHelper(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
boolean pIsOnLeft = covers(root.left, p);
boolean qIsOnLeft = covers(root.left, q);
if (pIsOnLeft != qIsOnLeft) { // Nodes are on different side
return root;
}
TreeNode childSide = pIsOnLeft ? root.left : root.right;
return ancestorHelper(childSide, p, q);
}
public static boolean covers(TreeNode root, TreeNode p) {
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
TreeNode root = TreeNode.createMinimalBST(array);
TreeNode n3 = root.find(1);
TreeNode n7 = root.find(7);
TreeNode ancestor = commonAncestor(root, n3, n7);
System.out.println(ancestor.data);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment