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!

This would be a much easier question if you showed the tree you were measuring (the one for which the answer is `a-c-f`) instead of some other tree. — GlenPeterson, Feb 16 '16 at 23:05
is your tree self balancing ... binary trees can be lots of things, if it isn't balanced, then you will have to basically go all the way left bottom then track along the bottom edge, with will have complexity proportionate to how pokey it is — Grady Player, Feb 17 '16 at 01:00

score 9 · Accepted Answer · edited Nov 10 '19 at 12:17

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)

Do you think there is a more efficient way to solve the problem? — coder_learner, Feb 17 '16 at 02:49
In order to find the max depth of the tree, we would have to traverse all the nodes in the tree, there's no other way. Thus, tree traversal has a time complexity of O(n). Your recursive implementation is doing just that, so no, I don't think there is a more efficient way! — kevchoi, Feb 17 '16 at 03:26
@kevchoi, I think you should remove `elif` condition, because 1. if node is leaf, 2. if left subtree is not null, 3. if right subtree is not null. So here you should not applied the `elif` condition, because it will cut some test cases.... — Neelabh Singh, Jan 25 '17 at 14:08
@kevchoi, I second @geeks suggestion. It is possible to not reach the `root.left is not None` conditional using elif statements. — Imjohsep, Mar 03 '17 at 04:24

score 3 · Answer 2 · answered Feb 17 '16 at 04:28

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

Boxi · Answer 3 · 2017-02-17T07:14:05.900

0

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 the recursive function will always pass print_path(root.left) if the right.root is not None.

edited Feb 17 '17 at 07:14

answered Nov 11 '16 at 07:32

Boxi

11
2

score 0 · Answer 4 · answered Jan 25 '17 at 14:41

My solution

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

score 0 · Answer 5 · answered May 03 '20 at 11:44

Below is a C++ implementation.

void longest_root_to_leaf_path(Node *root, std::vector<int> current_path,
                               std::vector<int> &longest_path) {         
  if (!root)                                                             
    return;                                                              

  current_path.push_back(root->data);                                    

  if (root->left == nullptr && root->right == nullptr) {                 
    if (current_path.size() > longest_path.size())                       
      longest_path = current_path;                                       
    return;                                                              
  }                                                                      

  longest_root_to_leaf_path(root->left, current_path, longest_path);     
  longest_root_to_leaf_path(root->right, current_path, longest_path);    
  current_path.pop_back();                                               
}

score -1 · Answer 6 · answered Nov 08 '16 at 09:56

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 like this the output would become [a,b] only which is not expected output

Print the longest path starting from root in a binary tree

6 Answers6