1650. Lowest Common Ancestor of a Binary Tree III

Practice Lowest Common Ancestor of a Binary Tree III for free on NudgeCode: Medium, Binary Tree pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

The original problem gives you only two nodes p and q of a binary tree, no root, but every node has a parent pointer. Return their lowest common ancestor: the deepest node that has both as descendants (a node counts as a descendant of itself).

This judge's TreeNode has no parent field, so the root is passed in too. Spend one pass over the tree recording each node's parent, then solve it the parent-pointer way: walk up from p and from q. The two upward chains are like two linked lists that merge, and the LCA is where they meet.

In the tests p and q are given by value; all values are unique. The expected output is the value of the node you return.

Example

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1  ->  3

Constraints

• 2 <= number of nodes <= 10^5
• p != q, and both exist in the tree