# 5 Best Ways to Find the Lowest Common Ancestor of a Binary Tree Using Python

Rate this post

π‘ Problem Formulation: Finding the lowest common ancestor (LCA) in a binary tree involves locating the lowest node in the tree that has two given nodes as descendants. For example, given a binary tree and two node values, the function should return the LCA node value. For input nodes 4 and 5 in a binary tree, where 2 is their LCA, the output should be 2.

## Method 1: Recursive Approach

The recursive approach involves breaking down the problem into smaller sub-problems. It checks if either of the two nodes matches the current node, then explores the left and right subtrees. The function specification should find and return the LCA node using recursion.

Here’s an example:

```class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

def findLCA(root, n1, n2):
if root is None:
return None
if root.val == n1 or root.val == n2:
return root
left_lca = findLCA(root.left, n1, n2)
right_lca = findLCA(root.right, n1, n2)

if left_lca and right_lca:
return root
return left_lca if left_lca is not None else right_lca

# Constructed binary tree is
#         1
#       /   \
#      2     3
#     / \   / \
#    4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

lca = findLCA(root, 4, 5)
print('LCA of 4 and 5 is', lca.val)
```

The output of this code snippet:

`LCA of 4 and 5 is 2`

This code defines a tree structure and a recursive function `findLCA()` to find the lowest common ancestor. The function recursively searches both sides of the tree and returns the node that is common to both paths leading to the given nodes.