Module assignment: Family tree toolkit in Python

What you will build

This assignment brings the whole module together in one program. You will build a family tree toolkit. A genealogy club stores its family trees as binary trees: each person has at most two recorded children, a left one and a right one. Members type questions one line at a time, and the program prints an answer for each line. Questions include how many generations the tree holds, how many people have no recorded children, how far apart two people are, and who the nearest shared ancestor of two people is.

You will need almost every idea from this module. Building the tree from a list of entries uses the builder from the first lesson, with a deque queue. The height, leaves and diameter questions use the recursion and the one-pass method from the second lesson. The right view uses the level-order walk from the third lesson. The shared ancestor and the distance use the recursive lowest common ancestor and its depth formula from the fourth lesson.

Treat this as a real program, not a set of loose exercises. Read the spec, build the parts one at a time, test each part with a small input, and only then put them together. The stages below show a sensible order. The reference solution at the end is hidden until you have tried the work yourself.

The spec

The program reads its input from standard input, which is the input box when you run it in the course. The input has three parts, in this order.

The first line holds a number N, the number of entries in the tree list. The second line holds the N entries, separated by spaces. The list uses the same rules as the builder in the first lesson. The first entry is the root. After it come the children, row by row from the top, and for each parent its left child comes before its right child. The word null marks a position with no node, and that position still uses up one entry. The list may stop after the last real node. If N is 0, the second line is blank, and the tree is empty. Every value in the tree is a different whole number.

The third part starts with a line that holds a number C, the number of commands. The next C lines each hold one command. The program prints exactly one output line for each command, in the same order as the commands.

These are the commands:

• height prints the height of the tree, counted in nodes. An empty tree has height 0.
• leaves prints the number of leaves. A leaf is a node with no children.
• diameter prints the diameter of the tree, counted in edges. An empty tree and a single node both have diameter 0.
• right prints the right view on one line, with the values separated by single spaces, from the top row down. It prints empty for an empty tree.
• lca P Q prints the value of the lowest common ancestor of P and Q. A node counts as its own ancestor. It prints missing if either value is not in the tree.
• distance P Q prints the number of edges on the path between P and Q. It prints missing if either value is not in the tree.

Any other command word prints unknown WORD, where WORD is the first word of the line. You may assume that the numbers in each command are whole numbers, and that each command line has the right number of words for its command.

Two rules are easy to miss. First, the output must be exact. Print no extra spaces at the end of a line and no blank lines. Second, distance is measured in edges, while height is measured in nodes. A path of three nodes has two edges, so check which unit each command asks for.

Sample inputs and expected outputs

Test your program on these three inputs before you submit anything. Each one is shown with the output it must produce. Compare your output with the expected text character by character.

Sample 1 covers most of the commands on a six-node tree:

7
1 2 3 4 5 null 6
7
height
leaves
diameter
right
lca 4 5
lca 4 9
distance 4 6

Expected output:

3
3
4
1 3 6
2
missing
4

The tree is the six-node tree from the first lesson. Its height is 3 and it has three leaves, 4, 5 and 6. Its diameter is 4 edges, the path 4, 2, 1, 3, 6. The right view is 1, 3 and 6. The lowest common ancestor of 4 and 5 is 2. The value 9 is not in the tree, so the query with 9 prints missing. The distance from 4 to 6 is 4 edges.

Sample 2 covers the empty tree and an unknown command. The blank second line is part of the input:

0
 
5
height
right
lca 1 2
distance 1 1
fly

Expected output:

0
empty
missing
missing
unknown fly

With no nodes, every value is missing, and the height is 0. The word fly is not a command, so it prints unknown fly.

Sample 3 covers a tree with a missing child in the middle of a row:

5
1 2 3 null 4
5
diameter
right
lca 4 3
distance 4 3
leaves

Expected output:

3
1 3 4
1
3
2

Here node 2 has no left child and a right child 4. Node 3 has no children, and node 4 has no children, so the leaves are 3 and 4. The longest path runs from 4 up to 2, up to 1, and down to 3, which has 3 edges. The right view takes the last node of each row, which is 1, then 3, then 4.

Requirements checklist

Copy this list into your notes, and tick each item only after you have tested it. The grading rubric below uses the same items.

• The program reads N, the N entries and the command count from standard input, and then reads one command per line.
• The tree is built with the rules from the first lesson, including null entries and a list that stops early.
• height prints the height in nodes, and 0 for an empty tree.
• leaves prints the number of leaves, and 0 for an empty tree.
• diameter prints the diameter in edges, and 0 for an empty tree.
• right prints the right view on one line, or empty for an empty tree.
• lca P Q prints the lowest common ancestor, or missing when either value is absent.
• distance P Q prints the number of edges between the two values, or missing.
• Any other command word prints unknown WORD and does not crash.
• The output has no extra spaces, no blank lines and no debug text.
• All three samples produce exactly the expected output.
• The program does not crash on an empty tree, a single node, or a value that is missing from the tree.

Reading the input in Python

The input has blank lines in it, and the blank line of an empty tree matters. That is why this assignment reads the input by lines and not by words. sys.stdin.read() returns all of the input as one string. .splitlines() cuts it into a list of lines, with one list item per line. Line 0 is N, line 1 is the entries, line 2 is C, and the commands start at line 3. The entries line is still there when N is 0, because it is the blank line.

The split() method, with no argument, cuts a line into words on any run of spaces. "lca 4 3".split() gives ["lca", "4", "3"]. The first word chooses the command, and the other words are the numbers.

Step-by-step plan

Build the program in four stages. After each stage, run it on sample 3, which is the smallest sample that uses a null in the middle. Only move on when that stage works.

Stage 1: read the tree and build it

Start by reading the input and building the tree. The program in this stage reads the tree list and prints its level order, so you can see whether the builder works before you add any commands. Type this into the input box, one line at a time:

5
1 2 3 null 4

import sys
from collections import deque
 
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build(tokens):
    if not tokens or tokens[0] == "null":
        return None
    root = TreeNode(int(tokens[0]))
    pending = deque([root])
    idx = 1
    while pending and idx < len(tokens):
        cur = pending.popleft()
        if idx < len(tokens) and tokens[idx] != "null":
            cur.left = TreeNode(int(tokens[idx]))
            pending.append(cur.left)
        idx += 1
        if idx < len(tokens) and tokens[idx] != "null":
            cur.right = TreeNode(int(tokens[idx]))
            pending.append(cur.right)
        idx += 1
    return root
 
 
def level_order(root):
    result = []
    if root is None:
        return result
    queue = deque([root])
    while queue:
        size = len(queue)
        level = []
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(level)
    return result
 
 
lines = sys.stdin.read().splitlines()
n = int(lines[0])
tokens = lines[1].split()[:n]
root = build(tokens)
print(level_order(root))

The output for that input is [[1], [2, 3], [4]]. If your output differs, check the builder first. The most common error at this stage is advancing idx only once per parent, which places every later value one slot too early. Each parent uses two positions, one for the left child and one for the right, even when one of them is null.

Stage 2: height, leaves and diameter

The next stage adds the three questions that use the whole tree. Each one is a short recursive function. The program below runs them on the six-node tree, with the tree built by hand, so you can test each function without reading input. Its output is what the first sample expects for those three commands.

The output is height 3, leaves 3 and diameter 4. Check the diameter carefully. Two of the three answers come from the simpler functions, but the diameter is the one most students get wrong. The best value must start at 0 for each tree, and the path must be measured in edges. If your diameter is one too big, you probably added 1 for the node itself. Keeping best inside diameter with nonlocal gives each call its own value, so an earlier tree cannot change a later answer.

Stage 3: the right view, the shared ancestor and the distance

The third stage adds the three questions that depend on specific values. The right view reuses the level-order walk. The lowest common ancestor and the distance both need a check that the values exist, because the recursive function returns a wrong answer when a value is missing. The program below answers those questions for the six-node tree and prints the answers with labels.

The output is right 1 3 6, lca 4 6: 1 and distance 4 6: 4. The distance check uses the formula from the fourth lesson: the depth of 4 is 2, the depth of 6 is 2, and the depth of the lowest common ancestor 1 is 0, so 2 + 2 - 0 gives 4. The line " ".join(...) joins the values with single spaces and adds no space at the end. Once you have this stage working, add the existence checks. Then lca and distance should print missing when a value is not in the tree, rather than a wrong number.

Stage 4: read the commands

The last stage connects the input to the functions. It reads the whole input, including the command count and the commands, and it dispatches each command to the function that answers it. The program below is the skeleton for that loop. It reads the same input format as the real program and echoes each command with a placeholder. Use it as the frame, and replace the placeholder with a call to the right function.

Type this into the input box:

5
1 2 3 null 4
5
diameter
right
lca 4 3
distance 4 3
leaves

import sys
 
lines = sys.stdin.read().splitlines()
count = int(lines[2])
for i, line in enumerate(lines[3:3 + count], 1):
    word = line.split()[0]
    print(f"command {i}: {word} (not built yet)")

The output is one line for each of the five commands. Two details in this skeleton matter for the real program. The count is on line 2, so the commands start on line 3, and the blank line of an empty tree is never read as a command. The split() call cuts each command into words, so lca 4 3 becomes the list ["lca", "4", "3"]. Use int on the second and third words for the numbers.

Grading rubric

Your work is graded out of 100. The three levels below describe what a solution at each grade looks like. Check your program against them before you submit.

A 60% solution reads the input and builds the tree correctly. It prints the correct answers for height, leaves and unknown commands, and it handles the empty tree in these three answers. It may print wrong answers for the other commands, or it may crash when a value is missing. Sample 2 is mostly correct, but the lca and distance lines may be wrong.

An 80% solution does everything in the 60% solution, and also prints correct answers for diameter, right and lca. The lca command checks that both values exist before it prints an answer, so it prints missing in the right cases. The distance command may be missing or wrong. Samples 1 and 3 are correct, except for the distance lines.

A 100% solution answers every command correctly, including distance, and passes all three samples with exact output. Its code is organised into small functions, one per question, with clear names. It has no debug output and no extra blank lines. It handles an empty tree, a single node, and a missing value without crashing. It also treats the blank line of an empty tree correctly, without reading a command from it. If you test on your own inputs as well as the samples, the program gives the answer that a careful hand calculation gives.

Hints

Use these hints only after you have tried each step on your own. Each one is hidden until you open it.

Show the hint: reading the input

Read all of the input with sys.stdin.read().splitlines(). Then lines[0] is N, lines[1] holds the entries, and lines[2] is the command count. Take the commands from lines[3:3 + count]. Remember that N can be 0, so the entries list can be empty. Use lines[1].split()[:n] so that you only take the first N words.

Show the hint: the empty tree

Make every question return its base-case answer when the root is None. height and leaves return 0. diameter returns 0. right checks for None and prints empty, because the level walk returns an empty list for None, and joining an empty list gives an empty line, not the word empty. lca and distance print missing because contains returns False for every value.

Show the hint: the existence check comes first

Call contains for both values before you call lca or depth. If either check fails, print missing and do not run the rest of the command. The recursive lca function gives an answer even when a value is missing, so the check is the only thing that tells you the answer is wrong.

Show the hint: distance from the LCA

Compute three depths: the depth of P, the depth of Q and the depth of their lowest common ancestor. Each depth comes from the depth function, which returns the number of edges from the root. The distance is depth_p + depth_q - 2 * depth_lca. Print that number with no decimal point, which int arithmetic gives you by default.

Show the hint: printing the right view

Build a list of the values, then join them with spaces. " ".join(str(v) for v in values) does this in one line. A join prints nothing extra, so the line has no trailing space.

Reference solution

Try the whole assignment before you open this. The reference solution is a complete program that reads the input and prints the answers. It uses the same functions as the four stages, plus a command loop that reads each command and dispatches it. Read it after you have finished your own version, and compare the two outputs on the samples. If they differ, find the first line where they differ, and check what your code does for that command.

Show the answer

import sys
from collections import deque
 
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build(tokens):
    if not tokens or tokens[0] == "null":
        return None
    root = TreeNode(int(tokens[0]))
    pending = deque([root])
    idx = 1
    while pending and idx < len(tokens):
        cur = pending.popleft()
        if idx < len(tokens) and tokens[idx] != "null":
            cur.left = TreeNode(int(tokens[idx]))
            pending.append(cur.left)
        idx += 1
        if idx < len(tokens) and tokens[idx] != "null":
            cur.right = TreeNode(int(tokens[idx]))
            pending.append(cur.right)
        idx += 1
    return root
 
 
def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))
 
 
def leaves(n):
    if n is None:
        return 0
    if n.left is None and n.right is None:
        return 1
    return leaves(n.left) + leaves(n.right)
 
 
def diameter(root):
    best = 0
 
    def walk(n):
        nonlocal best
        if n is None:
            return 0
        lh = walk(n.left)
        rh = walk(n.right)
        best = max(best, lh + rh)
        return 1 + max(lh, rh)
 
    walk(root)
    return best
 
 
def right_view(root):
    view = []
    if root is None:
        return view
    queue = deque([root])
    while queue:
        last = None
        for _ in range(len(queue)):
            last = queue.popleft()
            if last.left is not None:
                queue.append(last.left)
            if last.right is not None:
                queue.append(last.right)
        view.append(last.val)
    return view
 
 
def contains(n, v):
    if n is None:
        return False
    return n.val == v or contains(n.left, v) or contains(n.right, v)
 
 
def lca(n, p, q):
    if n is None:
        return None
    if n.val == p or n.val == q:
        return n
    a = lca(n.left, p, q)
    b = lca(n.right, p, q)
    if a is not None and b is not None:
        return n
    return a if a is not None else b
 
 
def depth(n, target, d=0):
    if n is None:
        return -1
    if n.val == target:
        return d
    f = depth(n.left, target, d + 1)
    if f != -1:
        return f
    return depth(n.right, target, d + 1)
 
 
def distance(root, p, q):
    if not contains(root, p) or not contains(root, q):
        return "missing"
    dp = depth(root, p)
    dq = depth(root, q)
    da = depth(root, lca(root, p, q).val)
    return str(dp + dq - 2 * da)
 
 
def main():
    lines = sys.stdin.read().splitlines()
    n = int(lines[0])
    tokens = lines[1].split()[:n]
    root = build(tokens)
    count = int(lines[2])
    answers = []
    for line in lines[3:3 + count]:
        parts = line.split()
        cmd = parts[0]
        if cmd == "height":
            answer = str(height(root))
        elif cmd == "leaves":
            answer = str(leaves(root))
        elif cmd == "diameter":
            answer = str(diameter(root))
        elif cmd == "right":
            answer = "empty" if root is None else " ".join(str(v) for v in right_view(root))
        elif cmd == "lca":
            p = int(parts[1])
            q = int(parts[2])
            if contains(root, p) and contains(root, q):
                answer = str(lca(root, p, q).val)
            else:
                answer = "missing"
        elif cmd == "distance":
            answer = distance(root, int(parts[1]), int(parts[2]))
        else:
            answer = f"unknown {cmd}"
        answers.append(answer)
    if answers:
        print("\n".join(answers))
 
 
main()

A short walk through the reference shows how the pieces fit together. main reads the tree and the commands, then loops over the command lines. Each line is split into words, and the first word chooses a branch of the if chain. The branch reads any numbers it needs, calls the function for that question, and stores the answer. The answers are collected in one list and printed at the end with one print call, which keeps the output exact and avoids printing in the middle of a loop. Notice that the right branch checks for an empty tree before it calls the level walk, and the lca and distance branches check for missing values before they call the recursive functions. The if answers: check at the end means a file with no commands prints nothing, not a blank line.

Before you submit

Run the program on all three samples, and compare each output line with the expected text. Then make one more test of your own, with a tree that has a single node and a command list that asks every question. Check the answers by hand before you run the program. A single node has height 1, 1 leaf, diameter 0, a right view of its one value, and distance 0 from itself. If your program agrees with your hand answers on that tree as well, you have tested the main paths and the edge cases.

Finally, read the requirements checklist once more and tick each item. Any item you cannot tick is a place to return to before you move on to the next module.