Get all branches(root to leaf) of a binary tree as lists in Python

Question

I've made a binary tree in Python in the form of a dictionary, in which every entry is of the form key: value. For example,

btree = {..., 
         node1: [value, nodeNoOfLeftChild, nodeNoOfRightChild],
         ... }

All nodes have the entries in the same format but some nodes can be missing too.

For example, if node number 5 has value X and child node numbers are 12 and 13, the entry looks like.

tree[5] = [X, 12, 13]

But it's possible that node 13 doesn't exist so node 5 only has one child. It is also possible that node 12 & 13 both do not exist, which makes node 5 a leaf node.

I want to get all the branches (root to leaf) of the tree as lists but the problem is the list length is variable depending upon the branching.

How do I make a function that takes in this dictionary and gives out lists?

Answer 1

Here's an example that uses your data structure and produces paths to each leaf node. To make it interesting, I chose to have the path consist of the names of the nodes. The path could just as easily be the node numbers. I'm not sure why a child node would have a number and yet not exist, so my example assumes that if a child node entry is non-zero, then the node exists:

from pprint import pprint

btree = {
    1: ["Node 1", 2, 3],
    2: ["Node 2", 4, 0],
    3: ["Node 3", 0, 0],
    4: ["Node 4", 5, 0],
    5: ["Node 5", 6, 0],
    6: ["Node 6", 7, 0],
    7: ["Node 7", 0, 0],
}

def do_node(id, path, result):
    node = btree[id]
    if node[1] == 0 and node[2] == 0:
        # This node has no children, and is thus a leaf node, so add it to the result list
        result.append(path + [node[0]])
    else:
        # This is a non-leaf node, so process its children
        if node[1] != 0:
            do_node(node[1], path + [node[0]], result)
        if node[2] != 0:
            do_node(node[2], path + [node[0]], result)


def print_leaf_paths(tree):
    result = []
    do_node(1, [], result)
    pprint(result)

print_leaf_paths(btree)

The sample tree has two leaf nodes, one right away and one down 5 levels. The result is:

[['Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6', 'Node 7'],
 ['Node 1', 'Node 3']]