Algorithm to return length of 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 shortest branch of the binary tree.

Please provide the pseudocode for this algorithm.

Answer 1

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.

Answer 2

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 )
}

Answer 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

Answer 4

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.