What data structure does this function represent?

Question

I have the following function and I'm not really sure if they are implementing a Binary Tree or a B-Tree.

Here is the code:

def foo(x):
    if x:
        a, b, c = x
        return foo(a) + b + foo(c)
    else:
        return 0

Could anyone help me figuring out which data structures are being used?

Answer 1

That is indeed a binary tree but, to some (usually those more comfortable with pointers), a rather strange implementation. Each node of the tree is a 3-tuple holding:

• the entire left sub-tree as a 3-tuple, or a false-type value if there's no sub-tree;
• the value of this node; and
• the entire right sub-tree 3-tuple or false-type value.

Your foo function is actually summing up all the nodes, althoug I'd make a few minor changes:

def sum_tree(tpl):
    if tpl:
        return foo(tpl[0]) + tpl[1] + foo(tpl[2])
    return 0

# Construct tree for testing:
#          __42__          (42)
#         /      \
#        7        5        (12)
#       / \      /
#     12   17   3          (32)
#                          ----
#                          (86)

tree = [[[None, 12, [None, 7, None]], 17, None], 42, [[None, 3, None], 5, None]]
print(sum_tree(tree)) # Output is `86`.