Leaves On A Binary Search Tree

This solution is not as beautiful as I would like it to be. There is likely a faster, more elegant solution to this, and I will continue to work on that. However, here is the code I have written in Python:

total_sum = 0
class Node:
    def __init__(self, val):
        self.left_child = None
        self.right_child = None
        self.data = val

def binary_insert(tree, val):
    # insert val at root if tree is empty
    if tree is None:
        tree = Node(val)
    else:
        # if val is less than current node, 
        # insert val into left subtree
        if (tree.data > val):
            tree.left_child = binary_insert(tree.left_child, val)
        # else, insert val into right subtree
        else:
            tree.right_child = binary_insert(tree.right_child, val)
    return tree

def leaf_test(tree):
    global total_sum
    if(tree.left_child == None and tree.right_child == None): #leaf nodes will not have a left or right child
        total_sum+=tree.data
    elif(tree.left_child == None and tree.right_child != None):
        leaf_test(tree.right_child)
    elif(tree.right_child == None and tree.left_child != None):
        leaf_test(tree.left_child)
    else:
        leaf_test(tree.left_child)
        leaf_test(tree.right_child)

value_list = [4, 2, 1, 5, 6, 3, 7, 9, 8, 12, 10, 11, 13, 15, 14]
tree=Node(value_list[0])

for i in range(1,len(value_list)):
    binary_insert(tree, value_list[i])

leaf_test(tree)
print(total_sum)

Allow me to explain. First, we define our tree to be the node of the first element in our list - which really makes the first logic statement in binary insert irrelevant. After that, we insert our values into our tree using a for loop. After that, we write a function to recursively test for left and right nodes until they both are equal to None (a leaf node). Then we add the data of that node to a global variable "total sum".

This will create this tree , which you can also make manually if you can't figure out how to write it in code.

Either method will return the answer $\boxed{37}$

Contruct the binary tree as per the algorithm given.

Then, The data in the leaf nodes of binary tree B are 1, 3, 8, 11, 14 (from left to right).

And, so the sum of data in the leaf nodes = 1 + 3 + 8 + 11 +14 = 37

4 is the root node,the rest of elements depend on the logic of the binary tree,(every element greater than the node must be appended to the right and to the left if it's lesser)

I hate reasoning.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Node:
    def __init__(self, val):
        self.left_child = None
        self.right_child = None
        self.data = val

def binary_insert(tree, val):
    if tree is None:
        tree = Node(val)
    else:
        if (tree.data > val):
            tree.left_child = binary_insert(tree.left_child, val)
        else:
            tree.right_child = binary_insert(tree.right_child, val)
    return tree

values=[4, 2, 1, 5, 6, 3, 7, 9, 8, 12, 10, 11, 13, 15, 14]

tree=None
for value in values:
    tree=binary_insert(tree, value)

total=0
def getTotal(node):
    global total
    if node.left_child:
        getTotal(node.left_child)
    if node.right_child:
        getTotal(node.right_child)
    if not node.left_child and not node.right_child:
        total+=node.data

getTotal(tree)
print total