Lowest Common Ancestor
236 LCA - given 2 nodes and root in Binary tree
Time O(n), space O(h)
LCA - given 2 nodes with parent pointer in same binary tree
Get depths of each nodes, make deeper node to the same level of another
Time O(h), Space O(1)
LCA - given 2 nodes with parent pointer, optimize for close ancestor
Use Hashtable
Time and Space O(D0 + D1)
235 LCA with BST
Worst case O(h)
Keep search the root in range [node0, node1]
1123. Lowest Common Ancestor of Deepest Leaves
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.
Last updated
Was this helpful?