Tree DFS in C#: Path Sums, Diameter and Ancestors

Part 12 got to every node. This part is what you compute once you are there, and almost all of it comes down to a single distinction.

Every program below is complete, was run on .NET 10, and its output is pasted from the run.

Pattern 61 — Root-to-leaf paths

Collect every path from the root to a leaf, and find the ones summing to a target.

The path so far cannot be returned upwards — it is information from above. So it is carried down, in a list that is added to on the way in and removed from on the way out.

//           5
//         /   \
//        4     8
//       /     / \
//      11   13   4
//     /  \        \
//    7    2        1
TreeNode tree = new(5,
    new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
    new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));

// The path so far is CARRIED DOWN in a list that is mutated and then undone.
// That undo is the same move backtracking is built on — see part 15.
static void Paths(TreeNode? n, List<int> path, List<string> found, int target)
{
    if (n is null) return;

    path.Add(n.Value);

    bool isLeaf = n.Left is null && n.Right is null;
    if (isLeaf)
    {
        int sum = path.Sum();
        string mark = sum == target ? "  <- sums to " + target : "";
        found.Add($"{string.Join(" -> ", path),-22} = {sum,3}{mark}");
    }
    else
    {
        Paths(n.Left, path, found, target);
        Paths(n.Right, path, found, target);
    }

    path.RemoveAt(path.Count - 1);          // undo, so a sibling starts clean
}

List<string> found = [];
Paths(tree, [], found, 22);
foreach (string s in found) Console.WriteLine(s);

Console.WriteLine();
Console.WriteLine("A leaf is a node with NO children. A node with one child is not a leaf,");
Console.WriteLine("which is why 8 -> 4 -> 1 is a path and 8 -> 4 is not.");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

It prints:

5 -> 4 -> 11 -> 7      =  27
5 -> 4 -> 11 -> 2      =  22  <- sums to 22
5 -> 8 -> 13           =  26
5 -> 8 -> 4 -> 1       =  18

A leaf is a node with NO children. A node with one child is not a leaf,
which is why 8 -> 4 -> 1 is a path and 8 -> 4 is not.

path.RemoveAt(path.Count - 1) after the recursive calls is the whole pattern. Without it the list keeps every node ever visited and the second path is wrong. This is the same add-then-undo shape that all of part 15’s backtracking is built on, and it is worth recognising here first, on something small.

The other trap is the definition of a leaf. A leaf has no children at all. A node with exactly one child is not a leaf — that is why 8 -> 4 does not appear in the output but 8 -> 4 -> 1 does. Writing if (n.Left is null) return path.Sum(); treats a one-child node as a leaf and produces short paths that look almost right.

Cost: O(n) nodes visited; O(n·h) total if you materialise every path.

Reach for it when the answer is about complete routes from the root — path sum, all paths, the smallest string from a leaf.

Pattern 62 — What a recursion returns, and what it carries

This is the idea the rest of the part rests on.

TreeNode tree = new(5,
    new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
    new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));

// CARRIED DOWN: the parameter. Information flowing from the root towards leaves.
static void CarryDown(TreeNode? n, int depth, List<string> log)
{
    if (n is null) return;
    log.Add($"  node {n.Value,2} is at depth {depth}");
    CarryDown(n.Left, depth + 1, log);
    CarryDown(n.Right, depth + 1, log);
}

// RETURNED UP: the return value. Information flowing from leaves to the root.
static int ReturnUp(TreeNode? n)
{
    if (n is null) return 0;
    int left = ReturnUp(n.Left);
    int right = ReturnUp(n.Right);
    return 1 + Math.Max(left, right);       // needs BOTH children's answers first
}

List<string> log = [];
CarryDown(tree, 0, log);
Console.WriteLine("carried down (a parameter) — depth of each node:");
foreach (string s in log) Console.WriteLine(s);

Console.WriteLine($"\nreturned up (a return value) — height of the tree: {ReturnUp(tree)}");

Console.WriteLine();
Console.WriteLine("Depth is known on the way DOWN, before any child is examined.");
Console.WriteLine("Height is only known on the way UP, after both children have answered.");
Console.WriteLine("Deciding which one a quantity is tells you where the line goes.");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

It prints:

carried down (a parameter) — depth of each node:
  node  5 is at depth 0
  node  4 is at depth 1
  node 11 is at depth 2
  node  7 is at depth 3
  node  2 is at depth 3
  node  8 is at depth 1
  node 13 is at depth 2
  node  4 is at depth 2
  node  1 is at depth 3

returned up (a return value) — height of the tree: 4

Depth is known on the way DOWN, before any child is examined.
Height is only known on the way UP, after both children have answered.
Deciding which one a quantity is tells you where the line goes.

Depth is known on the way down. When you arrive at a node you already know how far you have come, and no child has been examined. It is a parameter.

Height is only known on the way up. You cannot say how tall a subtree is until both children have reported. It is a return value.

Deciding which one your quantity is tells you where the line goes in the function — before the recursive calls, or after them. Every problem in this part is an application of that one question:

Quantity	Direction
Depth, the path so far, a valid range	carried down, as a parameter
Height, subtree sums, node counts	returned up, as a value
Diameter, “best anywhere” answers	returned up, and recorded outside

That third row is the next pattern.

Pattern 63 — Diameter, where the answer is a side effect

The longest path between any two nodes. The catch is that it need not go through the root — and quite often does not.

//         1
//       /   \
//      2     3
//     / \
//    4   5
//   /     \
//  6       7
TreeNode tree = new(1,
    new TreeNode(2, new TreeNode(4, new TreeNode(6)), new TreeNode(5, null, new TreeNode(7))),
    new TreeNode(3));

// The longest path in a tree need not pass through the root. At every node the
// best path THROUGH it is left height + right height. The answer is the largest
// of those — which is a SIDE EFFECT of a function that returns something else.
int best = 0;

int Height(TreeNode? n, int depth)
{
    if (n is null) return 0;
    int left = Height(n.Left, depth + 1);
    int right = Height(n.Right, depth + 1);

    int through = left + right;                 // edges, counting through this node
    if (through > best)
    {
        best = through;
        Console.WriteLine($"{new string(' ', depth * 2)}node {n.Value}: left={left} right={right} -> path of {through} edges through it (new best)");
    }
    else
    {
        Console.WriteLine($"{new string(' ', depth * 2)}node {n.Value}: left={left} right={right} -> {through} edges, best stays {best}");
    }

    return 1 + Math.Max(left, right);           // the RETURN value is the height
}

Height(tree, 0);
Console.WriteLine($"\ndiameter: {best} edges");
Console.WriteLine("the path is 6 -> 4 -> 2 -> 5 -> 7, which never touches the root");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

It prints:

      node 6: left=0 right=0 -> 0 edges, best stays 0
    node 4: left=1 right=0 -> path of 1 edges through it (new best)
      node 7: left=0 right=0 -> 0 edges, best stays 1
    node 5: left=0 right=1 -> 1 edges, best stays 1
  node 2: left=2 right=2 -> path of 4 edges through it (new best)
  node 3: left=0 right=0 -> 0 edges, best stays 4
node 1: left=3 right=1 -> 4 edges, best stays 4

diameter: 4 edges
the path is 6 -> 4 -> 2 -> 5 -> 7, which never touches the root

At every node, the best path through that node is leftHeight + rightHeight. So walk the tree computing heights, and at each node check whether the path through it beats the best seen so far.

The function returns a height. The diameter is recorded in a variable outside it. Those are two different quantities and the function only returns one of them — which is exactly what makes this pattern feel strange the first time. Trying to return the diameter instead leads to a tangle, because a parent needs its child’s height, not its child’s best path.

Look at the trace. The best is set at node 2, and the root reports 4 edges without improving it. The answer is 6 -> 4 -> 2 -> 5 -> 7, and node 1 is not on it.

Cost: O(n), one pass.

Reach for it when the answer is “the best anywhere in the tree” rather than “the best from the root” — maximum path sum, longest univalue path, largest BST subtree. All the same shape.

Pattern 64 — Lowest common ancestor

The deepest node that has both targets somewhere below it.

//         3
//       /   \
//      5     1
//     / \   / \
//    6   2 0   8
//       / \
//      7   4
TreeNode tree = new(3,
    new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))),
    new TreeNode(1, new TreeNode(0), new TreeNode(8)));

// Return the node itself if found, otherwise whatever the children found.
// A node that hears back from BOTH sides is the meeting point.
static TreeNode? Lca(TreeNode? n, int a, int b)
{
    if (n is null) return null;
    if (n.Value == a || n.Value == b) return n;      // found one; stop descending

    TreeNode? left = Lca(n.Left, a, b);
    TreeNode? right = Lca(n.Right, a, b);

    if (left is not null && right is not null) return n;   // one on each side
    return left ?? right;                                   // pass the survivor up
}

foreach ((int a, int b) in new[] { (5, 1), (5, 4), (7, 4), (6, 8), (5, 5) })
    Console.WriteLine($"lca({a}, {b}) = {Lca(tree, a, b)!.Value}");

Console.WriteLine();
Console.WriteLine("lca(5, 4) is 5: a node is allowed to be its own ancestor, which is why");
Console.WriteLine("the search stops the moment it finds either value rather than going deeper.");

Console.WriteLine();
// In a BST you do not need any of that — the values tell you which way to go.
static TreeNode? LcaBst(TreeNode? n, int a, int b)
{
    while (n is not null)
    {
        if (a < n.Value && b < n.Value) n = n.Left;
        else if (a > n.Value && b > n.Value) n = n.Right;
        else return n;                    // they diverge here, or one IS here
    }
    return null;
}

TreeNode bst = new(6,
    new TreeNode(2, new TreeNode(0), new TreeNode(4, new TreeNode(3), new TreeNode(5))),
    new TreeNode(8, new TreeNode(7), new TreeNode(9)));
Console.WriteLine("in a BST, no recursion is needed at all:");
foreach ((int a, int b) in new[] { (2, 8), (2, 4), (3, 5) })
    Console.WriteLine($"  lca({a}, {b}) = {LcaBst(bst, a, b)!.Value}");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

It prints:

lca(5, 1) = 3
lca(5, 4) = 5
lca(7, 4) = 2
lca(6, 8) = 3
lca(5, 5) = 5

lca(5, 4) is 5: a node is allowed to be its own ancestor, which is why
the search stops the moment it finds either value rather than going deeper.

in a BST, no recursion is needed at all:
  lca(2, 8) = 6
  lca(2, 4) = 2
  lca(3, 5) = 4

Three lines do everything.

Return the node itself if it is one of the targets, and stop descending. Otherwise ask both children. If both come back non-null, the targets are on opposite sides and this node is the meeting point. Otherwise pass up whichever one was found.

lca(5, 4) returning 5 is not a bug. A node counts as its own ancestor, which is the usual definition and is why the search stops as soon as it finds either value rather than continuing down.

In a BST none of this is needed. Walk down comparing: if both targets are smaller go left, if both are larger go right, and the first node where they diverge — or which is one of them — is the answer. No recursion, O(h) time, O(1) space.

Cost: O(n) general, O(h) on a BST.

Reach for it when the question is about ancestry, or the distance between two nodes — which is depth(a) + depth(b) - 2 * depth(lca).

Pattern 65 — Validating a BST

The one almost everyone writes wrong first time.

//      5              5 is the root, and 4 sits in its RIGHT subtree.
//     / \             Every parent-child pair is individually fine.
//    1   6            The tree is still not a BST.
//       / \
//      4   7
TreeNode broken = new(5,
    new TreeNode(1),
    new TreeNode(6, new TreeNode(4), new TreeNode(7)));

TreeNode fine = new(5,
    new TreeNode(3, new TreeNode(1), new TreeNode(4)),
    new TreeNode(8, new TreeNode(6), new TreeNode(9)));

// WRONG: only compares a node with its immediate children.
static bool NaiveCheck(TreeNode? n)
{
    if (n is null) return true;
    if (n.Left is not null && n.Left.Value >= n.Value) return false;
    if (n.Right is not null && n.Right.Value <= n.Value) return false;
    return NaiveCheck(n.Left) && NaiveCheck(n.Right);
}

// RIGHT: every node inherits a range from its ancestors, and must fall inside it.
static bool Check(TreeNode? n, long low, long high)
{
    if (n is null) return true;
    if (n.Value <= low || n.Value >= high) return false;
    return Check(n.Left, low, n.Value) && Check(n.Right, n.Value, high);
}

foreach ((string name, TreeNode t) in new[] { ("broken", broken), ("fine  ", fine) })
    Console.WriteLine($"{name}   naive says {NaiveCheck(t),-5}   bounds say {Check(t, long.MinValue, long.MaxValue)}");

Console.WriteLine();
Console.WriteLine("The naive check passes the broken tree because 4 < 6 and 6 > 5 are both");
Console.WriteLine("true locally. Nothing ever told 4 that it had to be greater than 5.");
Console.WriteLine();
Console.WriteLine("Bounds narrow on the way down: going left caps the maximum at the node's");
Console.WriteLine("value, going right raises the minimum to it. That is carried-down");
Console.WriteLine("information, exactly like depth.");
Console.WriteLine();
Console.WriteLine("long is used for the bounds so a node holding int.MinValue still works.");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

It prints:

broken   naive says True    bounds say False
fine     naive says True    bounds say True

The naive check passes the broken tree because 4 < 6 and 6 > 5 are both
true locally. Nothing ever told 4 that it had to be greater than 5.

Bounds narrow on the way down: going left caps the maximum at the node's
value, going right raises the minimum to it. That is carried-down
information, exactly like depth.

long is used for the bounds so a node holding int.MinValue still works.

The naive version checks each node against its immediate children and passes a tree that is not a BST. In that tree, 4 < 6 is true and 6 > 5 is true, so every local check succeeds. But 4 is in the root’s right subtree, so it must exceed 5, and nothing local ever says so.

The fix is carried-down information, exactly like depth. Every node inherits a range. Descending left caps the maximum at the current value; descending right raises the minimum to it. A node outside its inherited range fails.

Two details. The bounds are long, so a node holding int.MinValue is still comparable — using int there means the sentinel collides with a legitimate value. And the comparisons are strict, because a BST as normally defined has no duplicates.

Cost: O(n) time, O(h) space.

Reach for it when validating any structural property that depends on ancestors rather than parents. “Is this a valid heap”, “is every node smaller than everything above it” — same shape.

What to remember

• Ask first whether the quantity travels down or up. Down means a parameter, up means a return value. That single question resolves most tree problems.

• Undo after the recursive calls. path.RemoveAt(path.Count - 1) is not tidying up, it is what makes a sibling’s path correct.

• A leaf has no children. A node with one child is not one, and treating it as one silently produces short paths.

• The diameter is a side effect, not a return value. The function returns height and records the best separately, because a parent needs the child’s height.

• The longest path often misses the root. If your solution only considers paths through the root, it is wrong on most trees.

• A node is its own ancestor. lca(a, a) is a, and the early return is what implements that.

• Validating a BST needs a range, not a parent comparison. The local check passes trees that are not BSTs, and it does so quietly.

Part 14 leaves trees for intervals — where the entire difficulty is whether you sort by the start or by the end.