Skip to content

Instantly share code, notes, and snippets.

@lodi-g
Last active June 26, 2024 14:09
Show Gist options
  • Save lodi-g/7e98dc3671b73c0ed064aa16112be6e4 to your computer and use it in GitHub Desktop.
Save lodi-g/7e98dc3671b73c0ed064aa16112be6e4 to your computer and use it in GitHub Desktop.
How to post code on Discord?
Use `my one line block` to post a one line block.
Use
```c
#include <stdio.h>
int main(void) {
printf("Hello, World!\n");
}
```
to post a multi-line block, where 'c' is the coding language (c, cpp, java, js, rust, etc)
@amitsharma2403
Copy link

amitsharma2403 commented Jun 26, 2024

/**
 * 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) {

        // check if root node is null. 
        if (root == null){
            return null;
        }

        int curr = root.val;
        
// if current node value is less than both p and q, means it LCA exists on the left  side. 
        if(curr < p.val && curr < q.val){
           return lowestCommonAncestor(root.right, p, q);
        }
// if current node value is greater than both p and q, means it LCA exists on the right  side. 
        if (curr > p.val && curr > p.val){
          return lowestCommonAncestor(root.left, p, q);
        }
        // otherwise return root because that will be the intersect point. 
        return root;

        // time complexity will be the height of the treee o(h) and space complexity will be (1). 
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment