[algorithm] How to find the lowest common ancestor of two nodes in any binary tree?

The following is the fastest way to solve this . Space complexity O(1) , Time complexity O(n). If

If a node has both left and right value as not null, then that node is your answer(3rd 'if' from top). While iterating if a value is found, as all the values are uniques and must be present, we don't need to search its descendants. so just return the found node that matched. if a node's both left and right branch contents null propagate null upwards. when reached top-level recursion, if one branch returned value, others do not keep propagating that value, when both returned not null return current node. If it reaches root level recursion with one null and another not null, return not null value, as the question, promises the value exists, it must be in the children tree of the found node which we never traversed.

class Solution {
    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 && right !=null) return root;
        if (left == null && right ==null) return null;
        return (left != null ? left : right);
    }
}

enter image description here

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to binary-tree

Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Difference between binary tree and binary search tree Heap vs Binary Search Tree (BST) C linked list inserting node at the end How to print binary tree diagram? With ' N ' no of nodes, how many different Binary and Binary Search Trees possible? How to implement a binary tree? Find kth smallest element in a binary search tree in Optimum way What are the applications of binary trees? How to find the lowest common ancestor of two nodes in any binary tree?

Examples related to complexity-theory

Differences between time complexity and space complexity? Determining complexity for recursive functions (Big O notation) How to find time complexity of an algorithm How can building a heap be O(n) time complexity? HashMap get/put complexity Big-oh vs big-theta Is log(n!) = T(n·log(n))? Time complexity of accessing a Python dict What are the differences between NP, NP-Complete and NP-Hard? What's the fastest algorithm for sorting a linked list?

Examples related to least-common-ancestor

How to find the lowest common ancestor of two nodes in any binary tree?