CODEWITHSUNDEEP
pythonrecursiontree
zeelol
zeelol

Reputation: 33

Find all paths in a binary tree

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?

Upvotes: 1

Views: 1544

Answers (3)

Zakir
Zakir

Reputation: 103

All you need is to use the recursive depth first search algorithm. Here is a solution using Java:

class NodePrintAllPath {
    int data;
    NodePrintAllPath left, right;

    public NodePrintAllPath(final int value) {
        this.data = value;
        this.left = this.right = null;
    }
}


public class PrintAllPathOfBinaryTreeBFS {

    public static void  main(String[] args){
        NodePrintAllPath root = new NodePrintAllPath(10);
        root.left = new NodePrintAllPath(8);
        root.left.left = new NodePrintAllPath(3);
        root.left.right = new NodePrintAllPath(5);
        root.right = new NodePrintAllPath(2);
        root.right.left = new NodePrintAllPath(2);

        int[] path = new int[1000];
        printAllPathUsingDFS(root,path,0);


    }

    private static void printAllPathUsingDFS(NodePrintAllPath root, int[] path, int pathLength) {
        if(root == null){
            return;
        }

        path[pathLength] = root.data ;
        pathLength++;

        if(root.left == null && root.right == null){
            printPath(path,pathLength);
        }
        printAllPathUsingDFS(root.left, path,pathLength);
        printAllPathUsingDFS(root.right,path,pathLength);

    }

    private static void printPath(int[] path, int pathLength) {
        for(int i =0; i< pathLength; i++){
            System.out.print(path[i]+" ");
        }
        System.out.println("");
    }
}

//Output

10 8 3 
10 8 5 
10 2 2

Upvotes: 0

asd asd
asd asd

Reputation: 146

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.

Upvotes: 2

Mulan
Mulan

Reputation: 135197

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']

Upvotes: 2

Related Questions