Validate Three Nodes

Tags

Validate Three Nodes

Category

Binary Search Trees

Difficulty

Hard

Problem Statement

Given three nodes in a Binary Search Tree — nodeOne, nodeTwo, and nodeThree — determine whether nodeTwo lies on the path between nodeOne and nodeThree. In other words, check if nodeTwo is a descendant of nodeOne and an ancestor of nodeThree, OR nodeTwo is a descendant of nodeThree and an ancestor of nodeOne. The nodes are guaranteed to be in the BST, and all node values are unique.

Intuition

There are two valid configurations: either nodeOne is an ancestor of nodeTwo and nodeTwo is an ancestor of nodeThree, or nodeThree is an ancestor of nodeTwo and nodeTwo is an ancestor of nodeOne. We can verify each configuration by searching from the potential ancestor to the potential descendant using BST search. The BST property allows us to search efficiently without visiting all nodes.

Approach

  1. Check configuration 1: Is nodeTwo a descendant of nodeOne AND is nodeThree a descendant of nodeTwo?
  2. Check configuration 2: Is nodeTwo a descendant of nodeThree AND is nodeOne a descendant of nodeTwo?
  3. To check if node B is a descendant of node A, start at A and perform a BST search for B's value. If we find B, it is a descendant.
  4. An optimization: check both directions simultaneously. Start searching from nodeOne toward nodeTwo and from nodeThree toward nodeTwo at the same time. If either search reaches nodeTwo first, then verify the other direction from nodeTwo.
  5. Return true if either configuration is valid.

Pseudocode

function validateThreeNodes(nodeOne, nodeTwo, nodeThree):
    if isDescendant(nodeOne, nodeTwo):
        return isDescendant(nodeTwo, nodeThree)
    if isDescendant(nodeThree, nodeTwo):
        return isDescendant(nodeTwo, nodeOne)
    return false

function isDescendant(ancestor, target):
    current = ancestor
    while current is not null and current != target:
        if target.value < current.value:
            current = current.left
        else:
            current = current.right
    return current == target

Optimized version (simultaneous search):

function validateThreeNodes(nodeOne, nodeTwo, nodeThree):
    searchOne = nodeOne
    searchThree = nodeThree

    while true:
        foundFromOne = searchOne == nodeTwo
        foundFromThree = searchThree == nodeTwo

        if foundFromOne:
            return isDescendant(nodeTwo, nodeThree)
        if foundFromThree:
            return isDescendant(nodeTwo, nodeOne)

        searchOneStuck = searchOne == null or searchOne == nodeThree
        searchThreeStuck = searchThree == null or searchThree == nodeOne

        if searchOneStuck and searchThreeStuck:
            return false

        if not searchOneStuck:
            searchOne = searchOne.left if nodeTwo.value < searchOne.value else searchOne.right
        if not searchThreeStuck:
            searchThree = searchThree.left if nodeTwo.value < searchThree.value else searchThree.right

Time & Space Complexity

  • Time: O(h) where h is the height of the BST. Each search traverses at most the height of the tree. O(log n) for balanced BSTs, O(n) for skewed BSTs.
  • Space: O(1) since we only use a constant number of pointers.

Key Insights

  • The BST property is essential — it allows O(h) ancestor-descendant checking without parent pointers.
  • There are exactly two valid configurations, so we only need two directional checks.
  • The simultaneous search optimization avoids redundant work when one direction fails early.
  • If searchOne reaches nodeThree or null without finding nodeTwo, that configuration is impossible.
  • This problem does not require finding the actual path, only verifying the ancestor-descendant relationships.

Edge Cases

  • nodeTwo is the root — it can only be an ancestor, not a descendant (unless nodeOne or nodeThree is the root, which cannot be since nodeTwo is).
  • nodeOne equals nodeThree — nodeTwo must be a descendant and ancestor of the same node, which is only possible if all three are the same node.
  • The three nodes form a straight line in the BST (all in the same left-right path).
  • nodeTwo is a leaf — it cannot be an ancestor of nodeOne or nodeThree (unless one of them equals nodeTwo).
  • The BST is heavily unbalanced, making searches take O(n) time.

Linked mentions