1644. Lowest Common Ancestor of a Binary Tree II

Description

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)". A descendant of a node x is a node y that is on the path from node x to some leaf node.

Constraints

• The number of nodes in the tree is in the range [1, 104].

• -109 <= Node.val <= 109

• All Node.val are unique.

• p != q

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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. A node can be a descendant of itself according to the definition of LCA.

Example 3

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 10

Output: null

Explanation: Node 10 does not exist in the tree, so return null.

Solutions

TreeNode

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

Solution 1

/**
 * Time complexity : O(N), where N is the number of nodes in the binary tree. 
 *    In the worst case 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 be N since the height of a 
 *    skewed binary tree could be N.
 */

class Solution {
    private int count = 0;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode lca = lcaHelper(root, p, q);
        return (count == 2)? lca: null;
    }
    
    private TreeNode lcaHelper(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        TreeNode left = lcaHelper(root.left, p, q);
        TreeNode right = lcaHelper(root.right, p, q);
        if(root == p || root == q) {
            count++;
            return root;
        }
        if(left != null && right != null) {
            return root;
        }
        return (left == null)? right: left;
    }
}

Follow up