Module: Binary Tree

You can refer to the Leetcode problem236. Lowest Common Ancestor of a Binary Tree

Problem Statement

Given a binary tree, find thelowest 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 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).”

Example 1:

Input:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output:3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output:5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Intuition

We need to find the common first parent which has bothp andq as descendants.

Consider the following Binary Tree:

Input: root:[1, 2, 3, 4, null, 5, 6, null, 7, null, 8, 9, 10, null, null, null, null,null, null, 11, 12]
p:8
q :11

• We can follow the recursivepre-order dfs traversal and go on comparing the current node with p and q.

if(root==null){returnnull;}

• For each/any given node(root), check:
  1. Ifroot isnull, then we returnnull.
  2. If the one of the nodes amongp andq isroot itself? It means we found a match and in that case, we need to return that node, the matched root.

So for this we can compare the theroot with both p and q.

if(root==p||root==q){returnroot;}

• If any of the target nodes p/q does not exist in left child, it will be null. And similarly for right child, it will be null.

• Once a match is found in either left or right subtree, it is returned back(upward) to the recursive call and then compared with counter part (left or right value). If both the values are found, let sayp is found in left subtree andq found in the right subtree, then the current root, parent of left and right is returned as lca.

• If none found, null will be returned.

• Follow the blue arrows, when8 is found(fromlca(root.right, 8, 11) of root node5), it is compared with left childnull and8 is returned from the call stack of root5.

• Similarly, node11 gets returned as a result of recursive call from root3.

• Finally, in the call stack of root node3, left node is8 and right node is11. These 2 values are compared and since both are present(not null), current root (3) is returned which returned back till Tree root1.

Complexity Analysis

Time complexity:O(N), whereN is the number of nodes in the binary tree. In the worst case(left skewed or right skewed) we might be visiting all the nodes of the binary tree.

Space complexity:O(N). This is because the maximum amount of space utilized by the recursion stack would beN since the height of a skewed binary tree could beN.

program

classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null){returnnull;}if(root==p||root==q){returnroot;}TreeNodelNode=lowestCommonAncestor(root.left,p,q);TreeNoderNode=lowestCommonAncestor(root.right,p,q);if(lNode==null)returnrNode;if(rNode==null)returnlNode;returnroot;}}

Test cases

[3,5,1,6,2,0,8,null,null,7,4]51[3,5,1,6,2,0,8,null,null,7,4]54[1,2]12

Related problems

• Lowest Common Ancestor of a Binary Tree II
• Lowest Common Ancestor of a Binary Tree III
• Lowest Common Ancestor of a Binary Tree IV

Problem Credit :leetcode.com