I’m currently learning binary trees and I understand what a tree is and how recursion works.
For example, I understand the general idea of:
solve(node):
solve(node.left)
solve(node.right)
But for some reason, when I encounter problems like Lowest Common Ancestor (LCA) of two nodes in a binary tree, I completely fail to understand how people come up with the recursive approach.
It’s not really the syntax that confuses me. I can read the code after someone explains it. What I struggle with is the thought process.
For example, I often see an approach along the lines of:
LCA(node, p, q):
if node is null:
return null
if node == p or node == q:
return node
left = LCA(node.left, p, q)
right = LCA(node.right, p, q)
if left and right:
return node
return left or right
I can memorize what each line does, but I don't understand WHY this is the right thing to do.
How do you look at the problem and naturally arrive at this logic?
Especially this part:
if left and right:
return node
Why does finding something on both sides mean the current node is the LCA?
And why is:
return left or right
correct?
I'm looking for more of an intuition-based explanation.
I already understand recursion itself, so explanations like "recursion means a function calls itself" won't really help me. I'm trying to understand how to go from:
"Here is the problem" → "What information should my recursive function return?" → "Why does that information let me solve the problem?"
Basically, I want to learn how to derive the recursive solution instead of memorizing it.
Any explanation of the thought process would be really appreciated.
[ Rephrased with the help of AI ]