How does The Interns Company match students with internships?

We use a combination of AI-powered matching algorithms and human expertise to connect students with internship opportunities that align with their skills, interests, and career goals.

Are the internship opportunities exclusive?

Yes, many of our partner companies offer positions exclusively through our platform that you won't find on public job boards or career sites.

Is there a cost to use The Interns Company?

Our basic matching service is free for students. Premium services like one-on-one interview coaching and resume reviews may have associated fees.

Lowest Common Ancestor of a Binary Search Tree

MediumAcceptance: 58.3%

Tree Depth-First Search Binary Search Tree Binary Tree

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Constraints:

The number of nodes in the tree is in the range [2, 10^5]
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the BST.

Input Format:

The root of a binary search tree
Two nodes p and q in the tree

Output Format:

Return the lowest common ancestor node of p and q

Examples:

Example 1:

Input:

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

Output:

Explanation:

The LCA of nodes 2 and 8 is 6.

Example 2:

Input:

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

Output:

Explanation:

The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input:

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

Output:

Explanation:

The LCA of nodes 2 and 1 is 2, since a node can be a descendant of itself according to the LCA definition.

Solutions

Recursive Approach

Time: O(h) where h is the height of the tree

Space: O(h) due to recursion stack

Use the BST property to navigate: if both nodes are less than the current node, recursively search the left subtree; if both are greater, search the right subtree; otherwise, the current node is the LCA.

Iterative Approach

Time: O(h) where h is the height of the tree

Space: O(1) as we only use a constant amount of extra space

An iterative approach that uses the BST property to navigate the tree without recursion.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

Start at root (6)
Check if both p (2) and q (8) are on the same side of root
p (2) < 6 and q (8) > 6, so they are on different sides
Since the nodes are on different sides of the root, root (6) is the LCA

Hints

Hint 1

Use the property of a BST: for any node, values in its left subtree are smaller and values in its right subtree are larger.

Hint 2

If both p and q are smaller than the current node, the LCA must be in the left subtree.

Hint 3

If both p and q are larger than the current node, the LCA must be in the right subtree.

Hint 4

Otherwise, the current node is the LCA.

Video Tutorial

Lowest Common Ancestor of a BST - Using BST Properties

YouTube•Learn the Lowest Common Ancestor of a Binary Search Tree solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize finding the lowest common ancestor in a BST by navigating through the tree based on BST properties.

Key visualization elements:

current node
p node
q node
LCA node found

Asked By

Amazon Microsoft Facebook Google LinkedIn Apple

Implementation Notes

This problem leverages the BST property to efficiently find the LCA. The key insight is that in a BST, we can determine which subtree contains both nodes by comparing their values with the current node's value.