Print the longest path starting from root in a binary tree

Question

In this tree:

     a
    / \
   b   d
  /   / \
 c   e   f
        /
       g

The longest path starting from the root would be a-d-f-g

Here is my attempt:

class Node:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

def print_path(root):
  if not root:
    return []
  if root.left is None:
    return [root.val].append(print_path(root.right))
  elif root.right is None:
    return [root.val].append(print_path(root.left))
  elif (root.right is None) and (root.left is None):
    return [root.val]
  else:
    return argmax([root.val].append(print_path(root.left)), [root.val].append(print_path(root.right)))

def argmax(lst1, lst2):
  return lst1 if len(lst1) > len(lst2) else lst2

if __name__ == '__main__':
  root_node = Node('a')
  root_node.left = Node('b')
  root_node.right = Node('c')
  root_node.right.right = Node('f')
  print print_path(root_node)

The tree in the main() function is not the example I have shown. For this tree the expected results would be a-c-f. This tree is shown below:

   a
  / \
 b   c
      \
       f

Right now, I get

TypeError: object of type 'NoneType' has no len()

I'm not sure how None is showing up there since I have base cases.

Thanks!

Answer 1

Here's a working implementation:

class Node:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

def print_path(root):
  rightpath = []
  leftpath = []
  path = []
  if root is None:
    return []
  if (root.right is None) and (root.left is None):
    return [root.val]
  elif root.right is not None:
    rightpath = [root.val] + print_path(root.right)
  elif root.left is not None:
    leftpath = [root.val] + print_path(root.left)
  return argmax(rightpath, leftpath)

def argmax(lst1, lst2):
  return lst1 if len(lst1) > len(lst2) else lst2


root_node = Node('a')
root_node.left = Node('b')
root_node.right = Node('c')
root_node.right.right = Node('f')
print print_path(root_node)

Couple of issues with your code:

1) checking root.left is None before (root.right is None) and (root.left is None) is incorrect - you'll never reach (root.right is None) and (root.left is None)

2) instead of returning immediately, you want to use recursion and compare both branches and then return the branch with the longest path so far

3) append appends in place, so you need to store it in a variable

Edit: Cleaner implementation (see comments)

class Node:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

def print_path(root):
  rightpath = []
  leftpath = []
  if root is None:
    return []
  rightpath = [root.val] + print_path(root.right)
  leftpath = [root.val] + print_path(root.left)
  return argmax(rightpath, leftpath)

def argmax(lst1, lst2):
  return lst1 if len(lst1) > len(lst2) else lst2


root_node = Node('a')
root_node.left = Node('b')
root_node.right = Node('c')
root_node.right.right = Node('f')
print print_path(root_node)

Answer 2

You can simplify your logic significantly by allowing one more level of recursion and letting the main logic handle what were (confusing) special cases before:

def print_path(root):
    if root is None:
        return []
    return [root.val] + argmax(print_path(root.right), print_path(root.left))