Find the distance between two nodes in a binary tree?

TreeNode LCA(TreeNode root, int n1, int n2) {

if (root == null) return null;

if (root.val == n1 || root.val == n2) return root;

TreeNode left = LCA(root.left, n1, n2);

Follow on:

TreeNode right = LCA(root.right, n1, n2);

if (left != null && right != null) return root;

return left ?? right;

int FindLevel(TreeNode root, int val, int level) {

if (root == null) return -1;

if (root.val == val) return level;

int left = FindLevel(root.left, val, level + 1);

if (left != -1) return left;

return FindLevel(root.right, val, level + 1);

int DistanceBetweenNodes(TreeNode root, int n1, int n2) {

TreeNode lca = LCA(root, n1, n2);

int d1 = FindLevel(lca, n1, 0);

int d2 = FindLevel(lca, n2, 0);

return d1 + d2;

Explanation:

Find Lowest Common Ancestor (LCA) then sum distances from LCA to each node.