Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)
Back To Back SWE
ยท
Beginner
ยท7y ago
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
๐น Intuitive Video Explanations
๐ Run Code As You Learn
๐พ Save Progress
โNew Unseen Questions
๐ Get All Solutions
Question: Given the root of a binary tree and 2 references of nodes that are in the binary tree, find the lowest common ancestor of the 2 nodes. The nodes do not have parent pointers.
The Approach
So there are many modulations of this problem where you can build a hashtable and make parent pointers, etc. We will focus on the recursive solution.
The Algorithm
The key is that we want to root ourselves at a node and then search left and then right for either of the 2 nodes given.
If we see either node, we will return it, if we do not find the node in a subtree search the value of null will be returned and bubbled up.
After we search both left and right we ask ourselves what our results mean.
If we found nothing to the left, we just bubble up what is on the right (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.
If we found nothing to the right, we just bubble up what is on the left (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.
If both the right and left result are not null, we have found our LCA.
Why?
We know it is an ancestor at the least but we definitely know it is the lowest common ancestor because we went bottom upwards, whatever we hit will be the LCA and it will bubble up.
Complexities
Time: O( n )
We will be touching the whole tree in the search, there are n nodes in the tree and we do O(1) work at each node. There are not exactly n calls though but I need to double check this...I need to solve the recurrence but oh well...we know it will stay linear in the asymptotic regard.
Space: O( h )
Stack usage at maximum will be the trees height. W
Watch on YouTube โ
(saves to browser)
Sign in to unlock AI tutor explanation ยท โก30
Playlist
Uploads from Back To Back SWE ยท Back To Back SWE ยท 59 of 60
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
โถ
60
4 Tips To Learn Java Programming As Fast As Possible As A Beginner
Back To Back SWE
3 Mistakes Beginners Make When First Learning Java and Android Development
Back To Back SWE
How To Get A Job At Google | The Ultimate Guide To Algorithmic/Coding Interviews
Back To Back SWE
The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)
Back To Back SWE
Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)
Back To Back SWE
The N Queens Problem using Backtracking/Recursion - Explained
Back To Back SWE
Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)
Back To Back SWE
How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)
Back To Back SWE
Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms
Back To Back SWE
The 0/1 Knapsack Problem (Demystifying Dynamic Programming)
Back To Back SWE
The Dutch National Flag Problem (The Quicksort "Band-Aid")
Back To Back SWE
Test If A Binary Tree Is Symmetric ("Symmetric Tree" on Leetcode)
Back To Back SWE
The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP String
Back To Back SWE
How To Permute A String - Generate All Permutations Of A String
Back To Back SWE
The Balanced Parentheses Problem - Classic Stack Problem ("Valid Parentheses" on Leetcode)
Back To Back SWE
KnuthโMorrisโPratt (KMP) Pattern Matching Substring Search - First Occurrence Of Substring
Back To Back SWE
Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)
Back To Back SWE
Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals
Back To Back SWE
Generate All Palindromic Decompositions Of A String ("Palindrome Partitioning" on Leetcode)
Back To Back SWE
Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)
Back To Back SWE
Merge K Sorted Arrays - Min Heap Algorithm ("Merge K Sorted Lists" on LeetCode)
Back To Back SWE
Partition To K Equal Sum Subsets From An Array of Integers - The Backtracking Approach
Back To Back SWE
Edit Distance Between 2 Strings - The Levenshtein Distance ("Edit Distance" on LeetCode)
Back To Back SWE
Total Ways To Decode A String - Recursive Dynamic Programming Approach ("Decode Ways" on LeetCode)
Back To Back SWE
The Change Making Problem - Fewest Coins To Make Change Dynamic Programming
Back To Back SWE
Compute The Next Permutation of A Numeric Sequence - Case Analysis ("Next Permutation" on Leetcode)
Back To Back SWE
Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)
Back To Back SWE
Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode)
Back To Back SWE
Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)
Back To Back SWE
The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode)
Back To Back SWE
Search A Maze For Any Path - Depth First Search Fundamentals (Similar To "The Maze" on Leetcode)
Back To Back SWE
Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
Back To Back SWE
Test If A Binary Tree Is Height Balanced ("Balanced Binary Tree" on LeetCode)
Back To Back SWE
Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)
Back To Back SWE
Increment An Integer Represented As An Array ("Plus One" on LeetCode)
Back To Back SWE
Merge 2 Sorted Lists - A Fundamental Merge Sort Subroutine ("Merge Two Sorted Lists" on LeetCode)
Back To Back SWE
Clone An Undirected Graph - The Utility of Hashtable Mappings ("Clone Graph" on Leetcode)
Back To Back SWE
Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution
Back To Back SWE
Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science
Back To Back SWE
Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)
Back To Back SWE
Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)
Back To Back SWE
Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal.
Back To Back SWE
What Is Asymptotic Analysis? And Why Does It Matter? A Deeper Understanding of Asymptotic Notation.
Back To Back SWE
An In-Depth Algorithmic Analysis of Bubble Sort. Best Case, Average Case, & Worst Case.
Back To Back SWE
Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)
Back To Back SWE
A Detailed Algorithmic Analysis of Insertion Sort. Best Case & Worst Case.
Back To Back SWE
Binary Tree Level Order Traversal - Drawing The Parallel Between Trees & Graphs
Back To Back SWE
Implement A Queue Using Stacks - The Queue ADT ("Implement Queue Using Stacks" on LeetCode)
Back To Back SWE
All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A Hashtable
Back To Back SWE
Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems
Back To Back SWE
Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition
Back To Back SWE
Minimum Window Substring: Utilizing Two Pointers & Tracking Character Mappings With A Hashtable
Back To Back SWE
Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions
Back To Back SWE
Asymptotic Notations 101: Big O, Big Omega, & Theta (Asymptotic Analysis Bootcamp)
Back To Back SWE
The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms
Back To Back SWE
Fast Multiplication: From Grade-School Multiplication To Karatsuba's Algorithm
Back To Back SWE
Search A 2D Sorted Matrix - Fundamentals of Search Space Reduction
Back To Back SWE
The Quicksort Sorting Algorithm: Pick A Pivot, Partition, & Recurse
Back To Back SWE
Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)
Back To Back SWE
Sort A K Sorted Array - Investigating Applications of Min/Max Heaps
Back To Back SWE
๐
Tutor Explanation
DeepCamp AI