Counting the length of each branch in a binary tree and print out the nodes traversed

Question

I'm trying to return the length of all the paths and the actual paths of a binary tree with the values ordered by the position of the leaf nodes from left to right.

For eg, for this binary tree (picture below), the answer should be [(3, '4‐2‐1'), (4, '8‐5‐2‐1'), (4, '9‐5‐2‐1'), (2, '7‐1')] because the paths to leaf nodes are "1‐2‐4" (length 3), "1‐2‐5‐8" (length 4) "1‐2‐ 5‐9" (length 4) etc.

I've tried using recursion (sample code below) to count the length of the path but keep getting a TypeError: unsupported operand type(s) for +: 'int' and 'list'.

    res = []
    count = 0

    if T== None:
        return 0

    lengthL = 1 + self._pathV2(T.leftT)
    lengthR = 1+ self._pathV2(T.rightT)

    count = lengthR + lengthL
    res.append(count)

Any help with solving this problem will be much appreciated!

DarrylG DarrylG · Accepted Answer · 2019-12-02T04:53:31

Since you didn't provide your complete code I couldn't create a coding example using your code.

I created a coding example by modifying code from https://www.geeksforgeeks.org/given-a-binary-tree-print-out-all-of-its-root-to-leaf-paths-one-per-line/ as follows.

class Node: 

    # A binary tree node has data, 
    # pointer to left child and a  
    # pointer to right child 
    def __init__(self, data): 
        self.data = data 
        self.right = None
        self.left = None

def dfs_paths(stack, root, paths = []): 
    """ Depth first search through the tree for paths ensures paths are ordered 
        by the position of the leaf nodes from left to right """

    if root == None: 
        return

    # append this node to the path array 
    stack.append(root.data) 
    if(root.left == None and root.right == None): 

        # append all of its  
        # root - to - leaf 
        paths.append(' '.join([str(i) for i in stack[::-1]]))

    # otherwise try both subtrees 
    dfs_paths(stack, root.left, paths) 
    dfs_paths(stack, root.right, paths) 
    stack.pop() 

def paths_with_counts(root):
    """ Add counts to paths """
    paths = []
    dfs_paths([], root, paths)  # depth first search for paths

    # Add count to paths i.e. ('4-2-1') => (3, '4-2-1')
    return list(map(lambda p: (len(p.split()), p), paths))

Example Usage

Generate Your Tree example

root = Node(1); 
root.left = Node(2); 
root.right = Node(7);
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(8)
root.left.right.right = Node(9)

print(paths_with_counts(root))

Output

[(3, '4 2 1'), (4, '8 5 2 1'), (4, '9 5 2 1'), (2, '7 1')]

Counting the length of each branch in a binary tree and print out the nodes traversed

1 Answers