Shortest branch in a binary tree?

Question

A binary tree can be encoded using two functions l and r such that for a node n, l(n) give the left child of n, r(n) give the right child of n.

A branch of a tree is a path from the root to a leaf, the length of a branch to a particular leaf is the number of arcs on the path from the root to that leaf.

Let MinBranch(l,r,x) be a simple recursive algorithm for taking a binary tree encoded by the l and r functions together with the root node x for the binary tree and returns the length of the shortest branch of the binary tree.

Give the pseudocode for this algorithm.

OK, so basically this is what I've come up with so far:

MinBranch(l, r, x)
{
    if x is None return 0

    left_one = MinBranch(l, r, l(x))

    right_one = MinBranch(l, r, r(x))

    return {min (left_one),(right_one)}
}

Obviously this isn't great or perfect. I'd be greatful if people can help me get this perfect and working - any help will be appreciated.

Answer 1

I doubt anyone will solve homework for you straight-up. A clue: the return value must surely grow higher as the tree gets bigger, right? However I don't see any numeric literals in your function except 0, and no addition operators either. How will you ever return larger numbers?

Another angle on the same issue: anytime you write a recursive function, it helps to enumerate "what are all the conditions where I should stop calling myself? what I return in each circumstance?"

Answer 2

You're on the right approach, but you're not quite there; your recursive algorithm will always return 0. (the logic is almost right, though...)

note that the length of the sub-branches is one less than the length of the branch; so left_one and right_one should be 1 + MinBranch....

Steping through the algorithm with some sample trees will help uncover off-by-one errors like this one...

Answer 3

What you've created can be thought of as a depth-first search. However, given what you're after (shortest branch), this may not be the most efficent approach. Think about how your algorithm would perform on a tree that was very heavy on the left side (of the root node), but had only one node on the right side.

Hint: consider a breadth-first search approach.

Answer 4

What you have there looks like a depth first search algorithm which will have to search the entire tree before you come up with a solution. what you need is the breadth first search algorithm which can return as soon as it finds the solution without doing a complete search

Answer 5

It looks like you almost have it, but consider this example:

      4

   3     5

When you trace through MinBranch, you'll see that in your MinBranch(l,r,4) call:

left_one = MinBranch(l, r, l(x))
         = MinBranch(l, r, l(4))
         = MinBranch(l, r, 3)
         = 0

That makes sense, after all, 3 is a leaf node, so of course the distance to the closest leaf node is 0. The same happens for right_one.

But you then wind up here:

return {min (left_one),(right_one)}
     = {min (0), (0) }
     = 0

but that's clearly wrong, because this node (4) is not a leaf node. Your code forgot to count the current node (oops!). I'm sure you can manage to fix that.

---

Now, actually, they way you're doing this isn't the fastest, but I'm not sure if that's relevant for this exercise. Consider this tree:

         4
       3   5
     2
   1

Your algorithm will count up the left branch recursively, even though it could, hypothetically, bail out if you first counted the right branch and noted that 3 has a left, so its clearly longer than 5 (which is a leaf). But, of course, counting the right branch first doesn't always work!

Instead, with more complicated code, and probably a tradeoff of greater memory usage, you can check nodes left-to-right, top-to-bottom (just like English reading order) and stop at the first leaf you find.