How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Find lowest common ancestor in tree | Microsoft Coding Question

Quick Overview

This question evaluates understanding of tree data structures and the lowest common ancestor concept, contrasting use of binary search tree ordering with the general binary tree case while requiring algorithmic time and space complexity reasoning in the Coding & Algorithms domain.

Find lowest common ancestor in tree

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the root of a binary search tree (BST) and two distinct nodes p and q that are guaranteed to exist in the tree. Task (BST case): - Find the lowest common ancestor (LCA) of nodes p and q. - The LCA is defined as the lowest (deepest) node in the tree that has both p and q as descendants (a node can be a descendant of itself). Assumptions: - The tree satisfies the BST property: for any node x, all nodes in the left subtree have values < x.val, and all nodes in the right subtree have values > x.val. - You may receive p and q as node references or as values; clarify with the interviewer, and handle one consistent version. Follow-up: - How would your approach change if the tree is a general binary tree **without** the BST property? - In the general binary tree case: - The tree may not be balanced. - Node values are not ordered. - p and q are still guaranteed to exist. Describe algorithms for both the BST and the general binary tree cases and analyze their time and space complexity.

Quick Answer: This question evaluates understanding of tree data structures and the lowest common ancestor concept, contrasting use of binary search tree ordering with the general binary tree case while requiring algorithmic time and space complexity reasoning in the Coding & Algorithms domain.

Lowest Common Ancestor in a BST

Given BST level-order values and two node values, return their LCA value.

Constraints

Inputs are Python literals matching the function signature.
Return a deterministic exact-match value.

Examples

Input: ([6,2,8,0,4,7,9,None,None,3,5], 2, 8)

Expected Output: 6

Explanation: Root split.

Input: ([6,2,8,0,4,7,9,None,None,3,5], 3, 5)

Expected Output: 4

Explanation: LCA in left subtree.

Hints

Use deterministic tie-breaking for prompts with multiple valid outputs.
For design-style APIs, simulate operations with explicit inputs.

Lowest Common Ancestor in a General Binary Tree

Given general level-order tree values and two node values, return their LCA value.

Constraints

Inputs are Python literals matching the function signature.
Return a deterministic exact-match value.

Examples

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

Expected Output: 3

Explanation: Root LCA.

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

Expected Output: 2

Explanation: Nested LCA.

Hints

Use deterministic tie-breaking for prompts with multiple valid outputs.
For design-style APIs, simulate operations with explicit inputs.

Quick Overview