Obtain all root to leaf paths in binary tree while also identifying directions

Question

I have to obtain all the root-to-leaf paths in a binary tree. Now this is usually an easy task, but now I have to identify the left and right nodes as well. That is, when I'm going into a node's left subtree, the node should be recorded in the path as !abc, where abc is node name. When going into the right subtree, the node should be recorded as is. So if my tree is 1(left)2 (right)3, then the two paths that must be saved are !1->2 and 1->3. This is my code:

def get_tree_path(root, paths, treepath):
    if not root:
        return
    if not root.left and not root.right:
        treepath.append(root.data)
        paths.append(treepath)
        
    if root.left:
        treepath.append('!'+root.data[0])
        get_tree_path(root.left, paths, treepath)

    if root.right:
        treepath.append(root.data[0])
        get_tree_path(root.right, paths, treepath)

This does obtain the paths. But the left and right subtree paths are all joined together. That is, for the example given above, I get [!1, 3, 1, 2] as output. I have tried many suggestions given here: print all root to leaf paths in a binary tree and binary search tree path list but I'm only getting more errors. Please help.

I had to make a few adjustments to my answer but it should work now. — Bongni

Bongni Bongni · Accepted Answer · 2021-01-16T12:18:20

The problem is that when you save your treepath to path you don't delete the contents of treepath.

To do that you need to create a new list for every recursive call:

if root.left:
    treepath_left = list(treepath)
    treepath_left.append('!'+root.data[0])
    get_tree_path(root.left, paths, treepath_left)

if root.right:
    treepath_right = list(treepath)
    treepath_right.append(root.data[0])
    get_tree_path(root.right, paths, treepath_right)

Obtain all root to leaf paths in binary tree while also identifying directions

1 Answers