Leetcode — 236. Lowest Common Ancestor of a Binary Tree

The link to the problem: https://leetcode.com/problems/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 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, 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 graph (photo credit to Leetcode)

Thoughts:

This problem is the transformation of 235. Lowest Common Ancestor of a Binary Search Tree.

Let us first see how to solve problem 235, then see how we can solve this one.

In problem 235, the given tree is a binary search tree (BST). It is easy to find the given two nodes in the tree since all the nodes will follow the rules of a BST. In BST, if node A’s value is greater than the root node’s value, then node A will be in the right subtree, vice versa.

Assume we have three nodes: the root of the tree, root, and the two given nodes, p and q.
There are only two steps if you want to find the LCA of p and q.

1. Use the value of three nodes to see if p and q are on the same side of the root. If p and q are on the different side, then the root is the LCA of p and q.
2. If p and q are on the same subtree of the current root, then we will replace the current root with its left node or right node depends on the side where p and q are at. Then repeats Step 1.

The below 3ms code beats 100% solving the problem 235 —

//Iteration Version ------------------------------------------------
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null)
        {
            if(root.val < p.val && root.val < q.val)
                root = root.right;
            else if(root.val > p.val && root.val > q.val)
                root = root.left;
            else
                return root;
        }
        return null;
    }
//Recursive Version ------------------------------------------------
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val <= root.val && q.val >= root.val)
            return root;
        if(p.val >= root.val && q.val <= root.val)
            return root;
        //then it means they are in the same side
        if(root.val > p.val)
            return lowestCommonAncestor(root.left,p,q);
        else
            return lowestCommonAncestor(root.right,p,q);
        
    }

Code Logic:

In problem 236, we need to use a different strategy since we don’t know where p and q will be even if we know their values.

Hence, the problem will be — how do we find where p and q will be?

Every time when we call the method, we will split the root into 2 paths — its left node and right node. Our goal is finding p and q from the given root. We will keep searching UNTIL the given root is null (dead-end) or until we find either p or q (task completed).

There are 4 cases that might happen in the method —

1. If the left subtree cannot find either p or q, that means it’s impossible that LCA is in here. We will return what we got in the right subtree.
2. If the right subtree cannot find either p or q, that means it’s impossible that LCA is in here. We will return what we got in the left subtree.
3. If both of the left subtree and right subtree can find one of the nodes, then it means the current root is the LCA we want to find.
4. If both of the left subtree and right subtree cannot find either p or q, we will just return null. This means that this root doesn’t contain p or q. LCA is impossible to be in the tree of the current root.

Below is the 4ms code that beats 100% —

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        if(root.val == p.val || root.val == q.val)
            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;
    }

👷Let’s see how we call the methods in the below example.

Inputs: 
root = [1,2,3,4,5,6,7,null,null,10,null,12,13]
p = 4
q = 10

p = 4, q = 10

✏️We use LCA to represent the method name lowestCommonAncestor.

Initial call: LCA( 1️⃣, 4️⃣, 🔟) -> right is null, return left 2️⃣
— left = LCA( 2️⃣, 4️⃣, 🔟) -> Both left’ and right’ are not null, return 2️⃣
— —left’ = LCA( 4️⃣, 4️⃣, 🔟) = 4️⃣
— —right’ = LCA( 5️⃣, 4️⃣, 🔟) -> right’’ is null, return left’’ 🔟
— — — left’’ = LCA( 🔟, 4️⃣, 🔟) = 🔟
— — — right’’ = LCA( null, 4️⃣, 🔟) = null
—right = LCA( 3️⃣, 4️⃣, 🔟) -> left’ is null, return right’ (null)
— — left’ = LCA( 6️⃣, 4️⃣, 🔟) -> left’’ is null, return right’’ (null)
— — — left’’ = LCA( 1️⃣2️⃣, 4️⃣, 🔟) -> left’’’ is null, return right’’’ (null)
— — — — left’’’ = LCA( null, 4️⃣, 🔟) = null
— — — — right’’’ = LCA( null, 4️⃣, 🔟) = null
— — — right’’ = LCA( 1️⃣3️⃣, 4️⃣, 🔟) -> left’’’ is null, return right’’’ (null)
— — — — left’’’ = LCA( null, 4️⃣, 🔟) = null
— — — — right’’’ = LCA( null, 4️⃣, 🔟) = null
— — right’ = LCA( 7️⃣, 4️⃣, 🔟) -> left’’ is null, we return right’’ (null)
— — — left’’ = LCA( null, 4️⃣, 🔟) = null
— — — right’’ = LCA( null, 4️⃣, 🔟) = null