Lowest Common Ancestor of a Binary Tree
Tags: leetcode java python javascript scala
Questions involving the binary tree data structure are very popular in tech interviews, and can be challenging and varied! A binary tree is a data structure consisting of a collection of nodes (starting at a root node), where each node consists of a value (data), together with a directed edges to at most two nodes (the "left child" and "right child"), with the additional conditions that no two edges point to the same node and no edge points to the root. I recently solved an interesting problem on binary tree.
Problem Statement
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)"1.
Testcase
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.
Example 3
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
- The number of nodes in the tree is in the range [2, 105].
- -109 <= Node.val <= 109
- All Node.val are unique.
- p != q
- p and q will exist in the tree.
Explanation
We traverse the left and right sub trees.
-
If current node is NULL, then we will return NULL since we have reached the end of tree.
-
If current node matches node p or q, then we return current node.
-
If the current node has node p in its left subtree and q in its right subtree or vice versa then the current node will be the lowest common ancestor.
-
If the current node has nodes p and q exclusively in its left subtree or right subtree, then we will return the left or right subtree accordingly.
Solution
Complexity
Time Complexity: O(N).
Space Complexity: O(1).
comments powered by Disqus