Lowest Common Ancestor Definition

Problem

Definition

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Examples

graph TD;
	6;
	6 --- 2;
	6 --- 8;
	2 --- 0;
	2 --- 4;
	8 --- 7;
	8 --- 9;
	4 --- 3;
	4 --- 5;
  

• LCA of 2 and 8 is 6
• LCA of 2 and 4 is 2

Problems

Binary Tree

Lowest Common Ancestor of a Binary Tree Lowest Common Ancestor of a Binary Tree 2 - Nodes may not exist in Tree Lowest Common Ancestor of a Binary Tree 3 - Given Parent Pointer Lowest Common Ancestor of a Binary Tree 4 - for array of nodes

BST

Lowest Common Ancestor of a Binary Search Tree

N-Ary Tree

Lowest Common Ancestor for a n-ary Tree