LCA in Binary Tree

Find the lowest common ancestor using one recursive traversal

Read Here
Targets:p=5q=1
Step0/10
Processed0
ResultLCA=?
Back To Trees List

Python Code

11        if not root or root is p or root is q:
●            return root
13 
14        left = self.lowestCommonAncestor(root.left, p, q)
15        right = self.lowestCommonAncestor(root.right, p, q)
16 
17        if left and right:
18            return root
19 
20        return left if left else right
21 
22if __name__ == "__main__":
Current Line (12): Base Case

Tree Structure

012345678
Operation:Enter

LCA Output

Current Node

-

Phase

Recursive Call

Result Status

Running
Step 1: Enter

Recursion Stack

Stack is empty. Click Next to begin!

Step Explanation

Ready to Start

Click "Next Step" to begin. We will recursively search for the lowest common ancestor.

  • > Start from lca(root, p, q).
  • > Watch how left and right returns combine at each node.
Unvisited
Left Search
Current
Merge
Right Search
Returned Up