How should I practice Lowest Common Ancestor in Ordered and Unordered Trees?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft phone screen problems in FastPrep.

Is Lowest Common Ancestor in Ordered and Unordered Trees associated with Microsoft?

FastPrep tags this as a Microsoft phone screen coding practice problem when the problem catalog has that company and stage context.

Lowest Common Ancestor in Ordered and Unordered Trees

Microsoft● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

You are given the root root of a binary tree, two distinct node values p and q, and a boolean isBst. Return the value of their lowest common ancestor.

A common ancestor has both target nodes in its subtree, allowing a node to be its own descendant. The lowest common ancestor is the common ancestor furthest from the root.

If isBst is true, the input is a strict binary search tree: every value in a node's left subtree is smaller and every value in its right subtree is larger.
If isBst is false, the input is an ordinary binary tree with no ordering guarantee. Its values must not be used to choose a search direction.

For this exercise, assume all node values are unique and both target values occur in the tree. The input uses level-order tree serialization with null for absent children.

What the interview report shared

The initial task used BST ordering. The follow-up removed that ordering and called for a general binary-tree solution using postorder traversal.

Function

lowestCommonAncestor(root: TreeNode, p: int, q: int, isBst: boolean) → int

Examples

Example 1

root = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 8isBst = truereturn = 6

The targets lie on opposite sides of the root, so their lowest common ancestor is 6.

Example 2

root = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 4isBst = truereturn = 2

Node 2 is an ancestor of node 4 and is also its own descendant.

Example 3

root = [2,1]p = 2q = 1isBst = truereturn = 2

The root is one of the targets and contains the other target below it.

Example 4

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

The ordinary tree has one target in each root subtree; no BST ordering may be assumed.

Example 5

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

Node 5 is itself a target and is an ancestor of node 4.

Example 6

root = [1,2]p = 1q = 2isBst = falsereturn = 1

The same self-descendant rule applies to an ordinary binary tree.

Constraints

For this exercise, assume the finite, acyclic tree contains 2 through 10^5 nodes.
-10^9 <= node.val <= 10^9, with all values unique.
p != q, and both values occur in the tree.
isBst is true only when the entire tree satisfies the strict BST ordering rule; false makes no ordering guarantee.