Print the longest path, starting from the root in the binary tree.

Question

In this tree:

a / \ bd / / \ cef / g 

The longest path starting at the root will be adfg

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 an example that I showed. For this tree, the expected results will be acf . This tree is shown below:

  a / \ bc \ f 

Now i get

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

I'm not sure how None appears there, since I have basic 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) 

A couple of problems with your code:

1) checking root.left is None before (root.right is None) and (root.left is None) is incorrect - you will 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.

3) append added in place, so you need to save it in a variable

Edit: Pure implementation (see comments)

 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 [] 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 greatly simplify your logic by allowing another level of recursion and letting the main logic handle what happened (confuses) special cases before:

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

Answer 3

The code should be edited as:

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

or a recursive function will always pass print_path (root.left) if right.root is not None.

Answer 4

My decision

 import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** *Longest Path from root to leaf Node * */ public class LongestPath { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); Node root =bt.constructTree(bt); List path = printPath(root); Iterator itr = path.iterator(); while (itr.hasNext()){ System.out.print(itr.next() +" "); } } public static List<Integer> printPath(Node root){ if(root ==null){ return null; } List<Integer> path = new ArrayList<>(); path.add(root.data); List result = getMaxList(printPath(root.left), printPath(root.right)); if(result!=null) { path.addAll(result); } return path; } public static List<Integer> getMaxList(List<Integer> list1, List<Integer> list2){ if(list1==null && list2==null){ return null; } if(list1==null){ return list2; } if(list2 == null){ return list1; } if(list1.size()> list2.size()){ return list1; }else { return list2; } } } 

Binary tree

 class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; /* Get width of a given level */ int getWidth(Node node, int level) { if (node == null) return 0; if (level == 1) return 1; else if (level > 1) return getWidth(node.left, level - 1) + getWidth(node.right, level - 1); return 0; } /* UTILITY FUNCTIONS */ /* Compute the "height" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(Node node) { if (node == null) return 0; else { /* compute the height of each subtree */ int lHeight = height(node.left); int rHeight = height(node.right); /* use the larger one */ return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1); } } /* Driver program to test above functions */ public Node constructTree( BinaryTree tree) { /* Constructed binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(8); tree.root.right.right.left = new Node(6); tree.root.right.right.right = new Node(7); return tree.root; } } 

OUTPUT 1 3 8 7

Answer 5

the above program was wrong in another case

 elif root.left is not None: leftpath = [root.val] + print_path(root.left) elif root.right is not None: rightpath = [root.val] + print_path(root.right) 

if you give so, the output will be [a, b], which is not expected to exit