dsa · medium

Lowest Common Ancestor of a Binary Tree

GreyOrangeTreeRecursion

Tree [val,left,right]. p and q are values present in the tree. Return the LCA value.

Arguments

• root — the binary tree; each node is [val, left, right] or None
• p — the first node value (present in the tree)
• q — the second node value (present in the tree)

**Example**

`` Input: [3,[5,[6,None,None],[2,[7,None,None],[4,None,None]]],[1,[0,None,None],[8,None,None]]] 5 1 Output: 3 ``

Constraints

Number of nodes in [2, 200] Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[3,[5,[6,None,None],[2,[7,None,None],[4,None,None]]],[1,[0,None,None],[8,None,None]]]
5
1

Expected:
3

Example 2

Input:
[3,[5,[6,None,None],[2,[7,None,None],[4,None,None]]],[1,[0,None,None],[8,None,None]]]
5
4

Expected:
5

Open in the Dojo editor