Lowest Common Ancestor BST

Medium

Lowest Common Ancestor in BST

Problem Statement

Given a binary search tree (BST) and two nodes in the tree, find the lowest common ancestor (LCA) of these two nodes.

Rules and Constraints

  • The binary search tree is non-empty and has the following properties:
    • Each node has a unique integer key.
    • For any node, all keys in the left subtree are less than the key in the node.
    • For any node, all keys in the right subtree are greater than the key in the node.
  • The input nodes are guaranteed to be in the BST.
  • The time complexity of the solution should be O(h), where h is the height of the tree.
  • The space complexity of the solution should be O(1), excluding the space required for recursive call stack.
  • The solution should find the lowest common ancestor of the two input nodes, which is the node that is furthest from the root and is an ancestor of both nodes.

Input Description

  • A binary search tree node with a key, a left child, and a right child.
  • Two nodes in the binary search tree.

Output Description

  • The lowest common ancestor of the two input nodes in the binary search tree.

Example

Input: {"root":[6,2,8,0,4,7,9],"p":2,"q":8} Output: 6

CompaniesMicrosoft
JavaScript

Login to write code

Solve problems, verify your skills, and earn XP.