The Down-and-Up Template in Python, Java and TypeScript

class Node:
    def __init__(self, value: int, left: Node | None = None, right: Node | None = None) -> None:
        self.value = value
        self.left = left
        self.right = right


def visit(root: Node | None) -> tuple[dict[int, int], int, int]:
    depths: dict[int, int] = {}
    longest = 0

    def walk(node: Node | None, depth: int) -> int:
        nonlocal longest
        if node is None:
            return -1
        depths[node.value] = depth
        left = walk(node.left, depth + 1)
        right = walk(node.right, depth + 1)
        longest = max(longest, left + right + 2)
        return max(left, right) + 1

    height = walk(root, 0)
    return depths, height, longest


tree = Node(5, Node(9, Node(4), Node(2, None, Node(8))), Node(7, None, Node(6)))
depths, height, longest = visit(tree)
print("depths:", " ".join(f"{value}:{depth}" for value, depth in depths.items()))
print("height of the root:", height)
print("longest path:", longest)

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

public class DownUp {
    static final class Node {
        final int value;
        final Node left;
        final Node right;

        Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        Node(int value) {
            this(value, null, null);
        }
    }

    static int walk(Node node, int depth, Map<Integer, Integer> depths, int[] longest) {
        if (node == null) {
            return -1;
        }
        depths.put(node.value, depth);
        int left = walk(node.left, depth + 1, depths, longest);
        int right = walk(node.right, depth + 1, depths, longest);
        longest[0] = Math.max(longest[0], left + right + 2);
        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {
        Node tree = new Node(5, new Node(9, new Node(4), new Node(2, null, new Node(8))), new Node(7, null, new Node(6)));
        Map<Integer, Integer> depths = new LinkedHashMap<>();
        int[] longest = {0};
        int height = walk(tree, 0, depths, longest);
        System.out.println("depths: " + depths.entrySet().stream()
                .map(entry -> entry.getKey() + ":" + entry.getValue())
                .collect(Collectors.joining(" ")));
        System.out.println("height of the root: " + height);
        System.out.println("longest path: " + longest[0]);
    }
}

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

function visit(root: TreeNode | null): { depths: Map<number, number>; height: number; longest: number } {
  const depths = new Map<number, number>();
  let longest = 0;

  function walk(node: TreeNode | null, depth: number): number {
    if (node === null) {
      return -1;
    }
    depths.set(node.value, depth);
    const left = walk(node.left, depth + 1);
    const right = walk(node.right, depth + 1);
    longest = Math.max(longest, left + right + 2);
    return Math.max(left, right) + 1;
  }

  const height = walk(root, 0);
  return { depths, height, longest };
}

const tree = new TreeNode(5, new TreeNode(9, new TreeNode(4), new TreeNode(2, null, new TreeNode(8))), new TreeNode(7, null, new TreeNode(6)));
const { depths, height, longest } = visit(tree);
console.log("depths: " + [...depths].map(([value, depth]) => `${value}:${depth}`).join(" "));
console.log("height of the root: " + height);
console.log("longest path: " + longest);