# Question

Formatted question description: https://leetcode.ca/all/236.html

 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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

_______3______
/              \
___5__          ___1__
/      \        /      \
6      _2      0        8
/  \
7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3.
Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

@tag-tree


# Algorithm

The very simple idea is to see where the two values are compared with root:

• Both values are on the left, then LCA is on the left
• Both values are on the right, then LCA is on the right
• One on the left and one on the right means that LCA is the current root node

# Code

• import javafx.util.Pair;
import java.util.Stack;

public class Lowest_Common_Ancestor_of_a_Binary_Tree {

public static void main(String[] args) {
Lowest_Common_Ancestor_of_a_Binary_Tree out = new Lowest_Common_Ancestor_of_a_Binary_Tree();
Solution s = out.new Solution();

TreeNode root = new TreeNode(3);
TreeNode p = new TreeNode(5);
TreeNode q = new TreeNode(1);

root.left = p;
root.right = q;

System.out.println(s.lowestCommonAncestor(root, p, q).val);

TreeNode root2 = new TreeNode(1);
TreeNode p2 = new TreeNode(2);

root2.left = p2;

System.out.println(s.lowestCommonAncestor(root2, p2, root2).val);

}

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null) {
return null;
}

if (root == p || root == q) { // key is here, especially when p is parent of q or vice-versa
return root;
}

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

if (left != null && right != null) {
return root;
} else if (left == null && right == null) {
return null;
} else if (left == null && right != null) {
return right;
} else { // left != null && right == null
return left;
}
}
}

// official oj solution https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/
class Solution {

private TreeNode ans;

public Solution() {
// Variable to store LCA node.
this.ans = null;
}

private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {

// If reached the end of a branch, return false.
if (currentNode == null) {
return false;
}

// Left Recursion. If left recursion returns true, set left = 1 else 0
int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;

// Right Recursion
int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;

// If the current node is one of p or q
int mid = (currentNode == p || currentNode == q) ? 1 : 0;

// If any two of the flags left, right or mid become True
if (mid + left + right >= 2) {
this.ans = currentNode;
}

// Return true if any one of the three bool values is True.
return (mid + left + right > 0);
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Traverse the tree
this.recurseTree(root, p, q);
return this.ans;
}
}

// official oj solution-2 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/
class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

// Stack for tree traversal
Deque<TreeNode> stack = new ArrayDeque<>();

// HashMap for parent pointers
Map<TreeNode, TreeNode> parent = new HashMap<>();

parent.put(root, null);
stack.push(root);

// Iterate until we find both the nodes p and q
while (!parent.containsKey(p) || !parent.containsKey(q)) {

TreeNode node = stack.pop();

// While traversing the tree, keep saving the parent pointers.
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}

// Ancestors set() for node p.
Set<TreeNode> ancestors = new HashSet<>();

// Process all ancestors for node p using parent pointers.
while (p != null) {
p = parent.get(p);
}

// The first ancestor of q which appears in
// p's ancestor set() is their lowest common ancestor.
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}

}

class Solution_iteration {

// Three static flags to keep track of post-order traversal.

// Both left and right traversal pending for a node.
// Indicates the nodes children are yet to be traversed.
private int BOTH_PENDING = 2;

// Left traversal done.
private int LEFT_DONE = 1;

// Both left and right traversal done for a node.
// Indicates the node can be popped off the stack.
private int BOTH_DONE = 0;

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();

// Initialize the stack with the root node.
stack.push(new Pair<TreeNode, Integer>(root, this.BOTH_PENDING));

// This flag is set when either one of p or q is found.
boolean one_node_found = false;

// This is used to keep track of the LCA.
TreeNode LCA = null;

// Child node
TreeNode child_node = null;

// We do a post order traversal of the binary tree using stack
while (!stack.isEmpty()) {

Pair<TreeNode, Integer> top = stack.peek();
TreeNode parent_node = top.getKey();
int parent_state = top.getValue();

// If the parent_state is not equal to BOTH_DONE,
// this means the parent_node can't be popped off yet.
if (parent_state != this.BOTH_DONE) {

// If both child traversals are pending
if (parent_state == this.BOTH_PENDING) {

// Check if the current parent_node is either p or q.
if (parent_node == p || parent_node == q) {

// If one_node_found was set already, this means we have found
// both the nodes.
if (one_node_found) {
return LCA;
} else {
// Otherwise, set one_node_found to True,
// to mark one of p and q is found.
one_node_found = true;

// Save the current top element of stack as the LCA.
LCA = stack.peek().getKey();
}
}

// If both pending, traverse the left child first
child_node = parent_node.left;
} else {
// traverse right child
child_node = parent_node.right;
}

// Update the node state at the top of the stack
// Since we have visited one more child.
stack.pop();
stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1));

// Add the child node to the stack for traversal.
if (child_node != null) {
stack.push(new Pair<TreeNode, Integer>(child_node, this.BOTH_PENDING));
}
} else {

// If the parent_state of the node is both done,
// the top node could be popped off the stack.
// Update the LCA node to be the next top node.
if (LCA == stack.pop().getKey() && one_node_found) {
LCA = stack.peek().getKey();
}

}
}

return null;
}
}

}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) return right;
if (right == null) return left;
return root;
}
}

• // OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// Time: O(N)
// Space: O(H)
class Solution {
bool findPath(TreeNode *node, TreeNode *target, vector<TreeNode*> &path) {
if (!node) return false;
path.push_back(node);
if (node == target) return true;
if (findPath(node->left, target, path) || findPath(node->right, target, path)) return true;
path.pop_back();
return false;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> a, b;
findPath(root, p, a);
findPath(root, q, b);
TreeNode *ans = nullptr;
for (int i = 0; i < a.size() && i < b.size() && a[i] == b[i]; ++i) ans = a[i];
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def lowestCommonAncestor(
self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
if root is None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
return root if left and right else (left or right)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root:
return root

left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)

if left and right:
return root

if root == p or root == q:
return root

if left:
return left
if right:
return right
return None


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left == nil {
return right
}
if right == nil {
return left
}
return root
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode | null,
q: TreeNode | null,
): TreeNode | null {
const find = (root: TreeNode | null) => {
if (root == null || root == p || root == q) {
return root;
}
const left = find(root.left);
const right = find(root.right);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
return right;
};
return find(root);
}


• /**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (!root || root == p || root == q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (!left) return right;
if (!right) return left;
return root;
};


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn find(
root: &Option<Rc<RefCell<TreeNode>>>,
p: &Option<Rc<RefCell<TreeNode>>>,
q: &Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_none() || root == p || root == q {
return root.clone();
}
let node = root.as_ref().unwrap().borrow();
let left = Self::find(&node.left, p, q);
let right = Self::find(&node.right, p, q);
match (left.is_some(), right.is_some()) {
(true, false) => left,
(false, true) => right,
(false, false) => None,
(true, true) => root.clone(),
}
}

pub fn lowest_common_ancestor(
root: Option<Rc<RefCell<TreeNode>>>,
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
Self::find(&root, &p, &q)
}
}