Find all paths in a binary tree

Question

I am trying to solve the coding question of "Given a binary tree, return all root-to-leaf paths."

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

I have seen one solution

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        allPath = []
        if root is None:
            return []
        self.find_all_paths_recursive(root, [], allPath)
        return allPath

    def find_all_paths_recursive(self, currNode, currPath, allPath):
        if currNode is None:
            return 
        currPath.append(currNode.val)
        if currNode.left is None and currNode.right is None:
            currOut = '->'.join([str(x) for x in list(currPath)])
            allPath.append(currOut)
        # traverse left sub tree
        self.find_all_paths_recursive(currNode.left, currPath, allPath)
        # traverse right sub tree
        self.find_all_paths_recursive(currNode.right, currPath, allPath)
        del currPath[-1]

Running the above code gave me the answer of ["1->2->5", "1->3"], whcih is correct.

I was thinking by changing the code block under if currNode.left is None and currNode.right is None: to

      if currNode.left is None and currNode.right is None:
            #currOut = '->'.join([str(x) for x in list(currPath)])
            #allPath.append(currOut)
            allPath.append(currPath)

should gave me the results [[1,2,5], [1,3]]. However, this change returned me the results [[],[]]. I wonder why this doesn't work?

asd asd · Accepted Answer · 2020-11-23T17:13:52.473

2

Since you want to adding the currPath directly, you have to add a copy of the currPath at that instant.

Like this:

if currNode.left is None and currNode.right is None:
    #currOut = '->'.join([str(x) for x in list(currPath)])
    # allPath.append(currOut)
    allPath.append(list(currPath))

EDIT:

Without adding list you are adding the original list object to allPath which will be updated due to recursion. Adding the list will make a copy of the original list object which will be saved and not further updated.

edited Nov 23 '20 at 17:13

answered Nov 22 '20 at 08:56

asd asd

146
8

Thanks, asd asd. could you please help me explain why without adding the list won't work? – zeelol Nov 22 '20 at 22:39
Without adding list you are adding the original list object to allPath which will be updated. Adding the list() will make a copy of the original list object which will be saved and not further edited. – asd asd Nov 23 '20 at 17:07

score 2 · Answer 2 · answered Nov 23 '20 at 15:03

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things variable reassignment, other mutations, and side effects.

Let's see what it would look like to implement btree in this way. Notice the node properties left and right can be set when a new node is constructed -

# btree.py

def empty():
  return None

class node:
  def __init__(self, val, left = empty(), right = empty()):
    self.val = val
    self.left = left
    self.right = right

def paths(t, p = ()):
  if not t:
    return
  elif t.left or t.right:
    yield from paths(t.left, (*p, t.val))
    yield from paths(t.right, (*p, t.val))
  else:
    yield "->".join(map(str, (*p, t.val)))

Here's your main program now -

# main.py

from btree import node, empty, paths

#    1
#  /   \
# 2     3
#  \
#   5

t = node(1, node(2, empty(), node(5)), node(3))

print(list(paths(t)))

['1->2->5', '1->3']

I don't think you have understood OP's question fully. please read it again. (OP expects `[[1,2,5], [1,3]]` but is getting `[[], []].` and wants to know why that's the case) — Tibebes. M, Nov 23 '20 at 15:09
Tibebes, some questions send us down the wrong path altogether — Mulan, Nov 25 '20 at 17:43

Find all paths in a binary tree

2 Answers2

Linked