THINK FIRST·CODE LATER

← All labs

Lowest common ancestor in a BST

Problem

Write BstAncestor. Read n and n keys into a BST, then pairs a b until the end of input. For each pair print the lowest common ancestor (the deepest node that has both keys in its subtree — a node counts as its own ancestor), the distance in edges between a and b, and the path from the root to a. If a key is not in the tree print a key is missing.

Use the BST property: starting at the root, if both keys are smaller go left, if both are larger go right, otherwise you are at the LCA.

For the input

9
50 30 70 20 40 60 80 35 45
35 45 20 45 60 80 30 35 20 99

the program prints

35 and 45: LCA 40, distance 2 edge(s)
  path to 35: 50 30 40 35
20 and 45: LCA 30, distance 3 edge(s)
  path to 20: 50 30 20
60 and 80: LCA 70, distance 2 edge(s)
  path to 60: 50 70 60
30 and 35: LCA 30, distance 2 edge(s)
  path to 30: 50 30
20 and 99: a key is missing

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d12-4-data-1.txt

9
50 30 70 20 40 60 80 35 45
35 45 20 45 60 80 30 35 20 99
What your program must print for d12-4-data-1.txt
35 and 45: LCA 40, distance 2 edge(s)
  path to 35: 50 30 40 35
20 and 45: LCA 30, distance 3 edge(s)
  path to 20: 50 30 20
60 and 80: LCA 70, distance 2 edge(s)
  path to 60: 50 70 60
30 and 35: LCA 30, distance 2 edge(s)
  path to 30: 50 30
20 and 99: a key is missing

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d12-4-data-1.txt

Windows PowerShell does not understand <:

Get-Content d12-4-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.