Algorithm to return length of shortest branch in a binary tree

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 shortest branch of the binary tree.

Please provide the pseudocode for this algorithm.

From stackoverflow

• Look at both branches. Find the length of the shortest path in each. Add one to the smaller and consider it to be the shortest branch.

  bdonlan : That would be essentially writing the code for you - just try translating what I wrote to code :)

  MatrixFrog : rachel: itrue's pseudocode is more or less the same as bdonlan's answer, and Alex Martelli's uses the same idea too. It might be a little hard to follow but draw out a sample tree and try to follow all three answers carefully. You'll probably want to take notes along the way so you don't get lost. Hopefully you will see that all three are doing the same thing (except the distinction of returning the branch itself vs. the length).

• function recurseMin(n)
  {
  if r(n) is null and l(n) is null, return 1
  if r(n) is not null, rightSum = recurseMin( r(n-1) )
  if l(n) is not null, leftSum = recurseMin ( l(n-1) )
  return 1 + min( leftSum, rightSum )
  }
  

  hughdbrown : recurseMin() appears to take an argument...

  Stefan Kendall : There's an "edit" button for a reason. Odd that three separate people would upvote without correcting this.

  hughdbrown : Also, you seem to have a lot of 1's. If you have a tree with three nodes (a root, left, and right, say), I think you get a count of 3. Root is 1 + min(leftSum, rightSum). leftSum is 1 + recurseMin(left). recurseMin(left) is 1. rightSum is the same. Yup, depth of 3.

• I see you've received answers on how to get the length of the shortest branch, but your homework assignment is actually to return the branch itself, presumably as a list of nodes. So, here's executable pseudocode (i.e., Python) to actually return the branch, using None to mean null:

  def MinBranch(l, r, x):
    if x is None: return []
    left_one = MinBranch(l, r, l(x))
    right_one = MinBranch(l, r, r(x))
    if len(left_one) < len(right_one):
      tail = left_one
    else:
      tail = right_one
    return [x] + tail
  

  hughdbrown : Nice one, Alex.

  Alex Martelli : @hugh, glad you liked it, and thanks!

• You can also find it in O(2^R) where R is the result. Useful if the tree is very unbalanced or infinite. It is <= O(N).

  You can do this with iterative-deepening DFS.