Lowest Common Ancestor of a Binary Search Tree

Try to solve the Lowest Common Ancestor of a Binary Search Tree problem.

We'll cover the following

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement#

Given a binary search tree with $n$ nodes, your task is to find the lowest common ancestor of two of its nodes, node1 and node2.

The lowest common ancestor of two nodes, node1 and node2, is defined as the lowest node in the binary search tree that has both node1 and node2 as descendants.

By definition, a node is a descendant of itself. For example, if node2 is a descendant of node1, and we know that node1 is a descendant of itself, then node1 will be the lowest common ancestor of node1 and node2.

Constraints:

$2 \leq n \leq 500$
$-10^3 \leq$ Node.data $\leq 10^3$
All Node.data are unique.
node1 $\neq$ node2
node1 and node2 exist in the tree.

Examples#

Lowest Common Ancestor of a Binary Search Tree

What is the lowest common ancestor of $4$ and $7$ in the following binary search tree?

Question 1 of 30 attempted

Drag and drop the cards to rearrange them in the correct sequence.

Start traversing from the root of the binary search tree.

Compare the values of node1 and node2 with the current node’s value.

If both values are greater, move to the right child. If both values are smaller, move to the left child.

Otherwise, if the current node’s value is between the values of node1 and node2, return the current node as the lowest common ancestor.

Continue the traversal until the LCA is found.

Python

usercode > LowestCommonAncestor.py

# Definition for a binary tree node
# class TreeNode:
#     def __init__(self, data):
#         self.data = data
#         self.left = None
#         self.right = None
from ds_v1.BinaryTree.BinaryTree import TreeNode
def lowest_common_ancestor(root, node1, node2):
    # Replace this placeholder return statement with your code
    return None

Enter to Rename, Shift+Enter to Preview

Input #1

Input #2

Input #3

Lowest Common Ancestor of a Binary Search Tree

Solution: Build Binary Tree from Preorder and Inorder Traversal

Solution: Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree

Statement#

Examples#

Understand the problem#

Figure it out!#

Try it yourself#