In this post we will solve LeetCode 235. Lowest Common Ancestor of a Binary Tree problem using Java.
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. 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).” Constraints: o The number of nodes in the tree is in the range [2, 10^5]. o -10^9 <= Node.val <= 10^9 o All Node.val are unique. o p != q o p and q will exist in the BST. Realated Topics: o Tree o Depth-First Search o Binary Search Tree o Binary Trea
We are given a Binary Search Tree (BST) and the pointers / references to two nodes in the tree. We need to return the Lowest Common Ancestor (LCA) node.
The requirements make a reference to a definition in Wikipedia regarding the definition of the lowest common ancestor. In a nutshell, the LCA is the closest node from the root of the BST common to the two specified nodes. In the first example provided by LeetCode, we are given nodes 2 and 8 so the LCA is 6.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
}
}
The signature for the function of interest has three arguments. The root of the BST and two nodes. We need to return the LCA node.
I will be generating the solution for the function of interest using Java and the VSCode IDE on a Windows computer. Due to this fact I will be generating a simple test scaffold that will read in the arguments, generate the BST, call the function of interest and display the result. I do this to keep the test cases in the same file as the solution. The simplest way to solve the problem is to use the online IDE provided by LeetCode. That way you do not need to generate the test scaffold which IS NOT PART OF THE SOLUTION!
6,2,8,0,4,7,9,null,null,3,5 2 8 main <<< strArr: [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] main <<< pVal: 2 main <<< qVal: 8 main <<< arr: [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] main <<< inOrder: 0 2 3 4 5 6 7 8 9 main <<< preOrder: 6 2 0 4 3 5 8 7 9 main <<< postOrder: 0 2 3 4 5 7 8 9 6 main <<< levelOrderTraversal: [[6], [2, 8], [0, 4, 7, 9], [3, 5]] main <<< p: (2) main <<< q: (8) <<< lca: (6) p: (2) q: (8) main <<< lowestCommonAncestor: (6) 6,2,8,0,4,7,9,null,null,3,5 2 4 main <<< strArr: [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] main <<< pVal: 2 main <<< qVal: 4 main <<< arr: [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] main <<< inOrder: 0 2 3 4 5 6 7 8 9 main <<< preOrder: 6 2 0 4 3 5 8 7 9 main <<< postOrder: 0 2 3 4 5 7 8 9 6 main <<< levelOrderTraversal: [[6], [2, 8], [0, 4, 7, 9], [3, 5]] main <<< p: (2) main <<< q: (4) main <<< lowestCommonAncestor: (2) 2,1 2 1 main <<< strArr: [2, 1] main <<< pVal: 2 main <<< qVal: 1 main <<< arr: [2, 1] main <<< inOrder: 1 2 main <<< preOrder: 2 1 main <<< postOrder: 1 2 main <<< levelOrderTraversal: [[2], [1]] main <<< p: (2) main <<< q: (1) main <<< lowestCommonAncestor: (2)
The test cases are separated by two blank lines.
The first three lines in each test case are inputs to generate the BST, followed by the value of the `p` and `q` nodes respectively.
Our test code displays the input values to make sure all is well so far. The BST is then created and populated. To make sure all is well, different tree traversals are performed and the results are displayed. The `p` and `q` nodes are then displayed. They will be used as arguments to the function of interest.
During execution some information is displayed in order to verify that the algorithm is doing what it is intended to do. Such statements ARE NOT PART OF THE SOLUTION.
The last line in each test case displays the LCA node.
/**
* Enhanced TreeNode class typically used
* to solve LeetCode binary tree problems.
*/
public class TreeNode {
// **** class members ****
int val;
int height;
TreeNode left;
TreeNode right;
/**
* Constructor.
*/
public TreeNode() {
}
/**
* Constructor.
*/
public TreeNode(int val) {
this.val = val;
this.height = 1;
}
/**
* Constructor.
*/
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
/**
* Return a string representation of this node.
*/
@Override
public String toString() {
// // **** value and height ****
// return "(" + val + "," + height + ")";
// **** value only ****
return "(" + val + ")";
}
}
This is the implementation of the TreeNode class used to build the BST. The implementation of the TreeNode class IS NOT PART OF THE SOLUTION. I had to implement it to be able to generate and manipulate the BST and associated nodes.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION
* @throws IOException****
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** create String[] with values for the BST ****
String[] strArr = br.readLine().trim().split(",");
// **** read value for p ****
int pVal = Integer.parseInt(br.readLine().trim());
// **** read value for q ****
int qVal = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
System.out.println("main <<< pVal: " + pVal);
System.out.println("main <<< qVal: " + qVal);
// **** generate an Integer[] to build BST ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null") || strArr[i].isEmpty())
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate the BST ****
BST bst = new BST();
bst.root = bst.populate(arr);
// ???? ????
System.out.println("main <<< inOrder: " + bst.inOrder(bst.root));
System.out.println("main <<< preOrder: " + bst.preOrder(bst.root));
System.out.println("main <<< postOrder: " + bst.postOrder(bst.root));
System.out.println("main <<< levelOrderTraversal: ");
System.out.println(bst.levelOrderTraversal(bst.root).toString());
// **** find node p in BST ****
TreeNode p = bst.findBT(bst.root, pVal);
// **** find node q in BST ****
TreeNode q = bst.findBT(bst.root, qVal);
// ???? ????
System.out.println("main <<< p: " + p);
System.out.println("main <<< q: " + q);
// **** call the function of interest and display result ****
System.out.println("main <<< lowestCommonAncestor: " + lowestCommonAncestor(bst.root, p, q));
}
I will not go into much detail of the test scaffold which IS NOT PART OF THE SOLUTION. It reads the input values, generates and populates the BST, finds the nodes `p` and `q` and passes all three objects as arguments to the function of interest. The result is then displayed.
Please note that all auxiliary functions used by the test scaffold may be found in the associated GitHub repository in the last few lines of this post.
/**
* Given a binary search tree (BST),
* find the lowest common ancestor (LCA) of two given nodes in the BST.
*
* Execution: O(n) - Space: O(1)
*
* Runtime: 9 ms, faster than 11.72% of Java online submissions.
* Memory Usage: 47 MB, less than 18.26% of Java online submissions.
*
* 27 / 27 test cases passed.
* Status: Accepted
* Runtime: 9 ms
* Memory Usage: 47 MB
*/
static public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// **** base case (we allow a node to be a descendant of itself) ****
if (root == null || root == p || root == q) return root;
// **** check if this node is the LCA ****
if (p.val < root.val && root.val < q.val ||
q.val < root.val && root.val < p.val) {
// ???? ????
System.out.println("<<< lca: " + root + " p: " + p + " q: " + q);
// **** return LCA ****
return root;
}
// **** visit left subtree ****
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
// **** visit right subtree ****
else {
return lowestCommonAncestor(root.right, p, q);
}
// // ???? ????
// System.out.println("<<< root: " + root + " left: " + left + " right: " + right);
// // **** visit root node ****
// if (left != null && right != null) return root;
// // **** return left or right node ****
// return left != null ? left : right;
}
We start with a base case.
Since we are using a BST we can reduce the search by finding the LCA earlier in the tree traversal using the fact that in a BST node values are in a specific order.
We then traverse the left subtree and then the right one. Note the condition is also based on the fact that this is a BST.
You can find some commented code towards the end of the function of interest. When I started the implementation I did not take advantage of the fact the tree is a BST. The first implementation was accepted but was at the slow end of the spectrum. At that point I started adding checks for the BST and the execution time dropped.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LowestCommonAncestorBST.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John