Maximum depth or height of a Binary tree

Question

The Following function is supposed to calculate the maximum depth or height of a Binary tree the number of nodes along the longest path from the root node down to the farthest leaf node.

please comment as if it was a 15 minute coding interview. coding style and efficiency.

this was given to you

public class BinaryTreeNode
{
    public BinaryTreeNode Left { get; set; }
    public BinaryTreeNode Right { get; set; }
    public int Value { get; set; }

}

please comment on the unit tests as well.

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    [TestClass]
    public class MaxTreeDepth
    {
        //     0 
        //   1    2
        //  3
        [TestMethod]
        public void GetMaxTreeDepthTest()
        {
            BinaryTreeNode root = new BinaryTreeNode
            {
                Value = 0,
                Left = new BinaryTreeNode {Value = 1},
                Right = new BinaryTreeNode {Value = 2}
            };
            root.Left.Right = new BinaryTreeNode {Value = 3};

            int result = GetMaxTreeDepth(root);
            Assert.AreEqual(3,result);
        }

        //     0 

        [TestMethod]
        public void GetMaxTreeDepthTestOneNode()
        {
            BinaryTreeNode root = new BinaryTreeNode
            {
                Value = 0,
            };

            int result = GetMaxTreeDepth(root);
            Assert.AreEqual(1, result);
        }

        [TestMethod]
        [ExpectedException(typeof(ArgumentNullException))]
        public void GetMaxTreeDepthTestNull()
        {
            BinaryTreeNode root = null;
            int result = GetMaxTreeDepth(root);
        }

        private int GetMaxTreeDepth(BinaryTreeNode root)
        {
            if (root == null)
            {
                throw new ArgumentNullException();
            }
            int depth = 0;
            return GetMaxHelper(root, depth);
        }

        private int GetMaxHelper(BinaryTreeNode root, int depth)
        {
            if (root == null)
            {
                return depth;
            }

            return Math.Max( GetMaxHelper(root.Right, depth+1),  GetMaxHelper(root.Left, depth+1));
        }
    }
}

Answer 1

(I won't comment on the prescribed BinaryTreeNode definition)

API

Both GetMaxTreeDepth and GetMaxHelper can, and arguably should, be static, as they have no logical dependencies. GetMaxTreeDepth should of course be in some way public (i.e. expose an API), and GetMaxHelper should remain private/internal as an implementation detail.

There is little documentation here, and inline documentation (///) of public APIs is invaluable for discoverability and usability. In particular, I'd expect the throw-on-null documented, and a precise statement of the return value (e.g. I might expect that null would return 0, and a tree with only one node and no children return 1, but I'd be wrong). If I was feeling helpful, I might add note clarifying that it is a tree search, and that passing a graph with cycles is not supported (it will eventually crash with a stack-overflow); it is stated that you are processing a binary tree, but the definition you are given is clearly not going to prevent anyone building a graph.

I don't know if it was clarified in the question statement, but throwing on null is a design decision, and isn't something you can assume as an implementer (certainly not without documentation to go with the assumption). This is also not the most helpful exception ever:

throw new ArgumentNullException();

Which argument? Granted there is only one, but this could have bubbled up from an internal method which takes some parameter which is a function of root. Everyone will be happier if you tell them exactly how it was they violated your API's contract:

throw new ArgumentNullException(nameof(root), "Ideally a helpful message here, unless it's just going to state the obvious and create confusion");

Recursion

Recursion is always dodgy*: you don't know where you might end up, and it could well be a stack overflow. As a 'quick and easy' implementation this looks fine (and is easy to understand), but for production code I would consider an iterative solution using an explicit stack, as this can be considerably more space efficient and cope with much deeper trees. A reasonable iterative solution will almost certainly also be faster for larger trees.

GetMaxHelper

I'd break that last line of GetMaxHelper out a bit, making it clearer and easy to read in a narrow window. I'd be inclined to change root to node or something less important sounding also, since root sounds like it should be at depth 0 (or 1?), and these guys are not necessarily so.

int leftDepth = GetMaxHelper(node.Left, depth + 1);
int rightDepth = GetMaxHelper(node.Right, depth + 1);
return Math.Max(leftDepth, rightDepth);

We could probably argue all day about where the depth++ bit should go, so I won't.

Tests

It's good that you are testing boundary conditions, but you really need more comprehensive tests than this (I guess this is where the 15min time-limit shows up). An implementation where you 'forgot' to look down the right-hand branches, or made a C&P error (like I did when writing the above snippet) to the same effect would pass your tests.

Sorry, just noticed that you do use a right-hand branch; it's just that your diagram for GetMaxTreeDepthTest is misleading, only showing left-hand branches (which is obviously not ideal). There is value, however, in having tests which explicitly test different bits of logic (e.g. if you have one which only worries about left-branches, and another which only worried about right-branches, you can single out some class of problems more quickly).

Boring Stuff

The int depth = 0 is clearly redundant, and though that wouldn't bother me, you might consider a named argument or default (= 0) parameter to avoid leaving a variable floating around or to avoid misusing the method by accident. (That said, I seem to spend most of my life regretting using default parameters, so I wouldn't be tempted)

This spacing is inconsistent:

 return Math.Max( GetMaxHelper(root.Right, depth+1),  GetMaxHelper(root.Left, depth+1));

As is this:

Assert.AreEqual(3,result);

---

* unless it's a tail-call in an explicitly tail-call optimising language, of course