Given a binary tree, find the longest possible path.

tree_path.cc

// Given a binary tree, find the longest possible path.
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <random>

struct Node {
  int id;
  Node* left;
  Node* right;
};

template<class RandGenerator>
Node* MakeRandomTree(RandGenerator& rand, int& next_id, int depth=0) {
  std::uniform_real_distribution<double> dist(0, 1);
  const double p = depth < 3 ? 0.2 : 0.7;
  if (dist(rand) < p)
    return nullptr;

  int id = next_id++;
  return new Node {
    id,
    MakeRandomTree(rand, next_id, depth+1),
    MakeRandomTree(rand, next_id, depth+1)
  };
}

void PrintTree(Node* node, int depth=0) {
  if (!node)
    return;

  PrintTree(node->left, depth+1);
  for (int i = 0; i < depth; ++i)
    std::cout << "   ";
  std::cout << node->id << std::endl;
  PrintTree(node->right, depth+1);
}

struct LeafPath {
  int left_len;
  int right_len;
  Node* left_end;
  Node* right_end;
  Node* center;
};

struct LeafDepth {
  Node* leaf;
  int depth;
};

LeafDepth SolveRec(Node* node, LeafPath& max_path) {
  if (!node)
    return LeafDepth { nullptr, -1 };

  LeafDepth left_leaf = SolveRec(node->left, max_path);
  if (!left_leaf.leaf)
    left_leaf.leaf = node;
  ++left_leaf.depth;

  LeafDepth right_leaf = SolveRec(node->right, max_path);
  if (!right_leaf.leaf)
    right_leaf.leaf = node;
  ++right_leaf.depth;

  if (left_leaf.depth + right_leaf.depth > max_path.left_len + max_path.right_len) {
    max_path = LeafPath {
      left_leaf.depth,
      right_leaf.depth,
      left_leaf.leaf,
      right_leaf.leaf,
      node
    };
  }

  return left_leaf.depth > right_leaf.depth ? left_leaf : right_leaf;
}

LeafPath Solve(Node* root) {
  LeafPath max_path = { 0, 0, root, root, root };
  SolveRec(root, max_path);
  return max_path;
}

int main(int argc, char* argv[]) {
  std::mt19937 rand;
  rand.seed(argc > 1 ? atoi(argv[1]) : 0);
  int id = 0;
  Node* root = MakeRandomTree(rand, id);
  if (!root) {
    std::cout << "oops empty tree\n";
    return -1;
  }

  PrintTree(root);

  LeafPath max_path = Solve(root);
  std::cout << "max_path_len "
            << max_path.left_len + max_path.right_len << std::endl
            << "center: " << max_path.center->id << std::endl
            << "left_end: " << max_path.left_end->id << std::endl
            << "left_len: " << max_path.left_len << std::endl
            << "right_end: " << max_path.right_end->id << std::endl
            << "right_len: " << max_path.right_len << std::endl;

  return 0;
}