Hadron DaVinci

Sum of Numbers in Binary Tree Paths

21 Nov 2020 - Hadron DaVinci

Problem
Find the sum of all the numbers represented by a binary tree given that each node represents a digit in numbers formed by paths from root to leaf.

Problem

Find the sum of all the numbers represented by a binary tree given that each node represents a digit in numbers formed by paths from root to leaf.

Example

Binary tree data as text: 6 3 2 ~ ~ 5 7 ~ ~ 4 ~ ~ 5 ~ 4 ~ ~

• Null nodes are represented by ~
• data is stored as a preorder
  

Truths

1. Each node is a digit -Therefore it will be between [0, 9]
2. The digit at leaf node always represents a decimal place value of 1
3. The digit at root node has a decimal place value that increases the longer the root-to-leaf path is

Method

Use the preorder input to create binary tree and while creating tree, track the history of digits.
When at a leaf node, convert number history to a number and add it to a running total.

TC: O(n)
SC: O(n)

Steps:

• Define Binary Tree Node

class BinaryTreeNode:
    def __init__(self, digit: int, left=None, right=None):
        self.data = digit
        self.left = left
        self.right = right

• Define Binary Tree Node

class BinaryTree:
    def __init__(self, node_list: list, null_char: str = "~") -> None:
        self.null_node_char = null_char
        self.node_list = node_list
        self.index = 0
        self.total_sum = 0
        self.root = self.insert_next_node()

• Define Method That Builds Tree

  Code recursively builds tree and returns the root node.
  It can return the root node b/c the first element represents the root node.
  What’s important here is that the code appends the current digit to the number history
  and passes the number history information to the children.

  For each node in node list, code does the following:

• extracts data from the node list
• creates new BinaryTreeNode
  • does this only if the extracted data is not the Null character, ‘~’
• increments build index
  • that way, when the insert_next_node method is called again, it will
    try to insert the next node in node list
• immediately inserts the left node (And All Its Children)
• inserts the right node (And All Its Children)
• if this node doesn’t have any children, then convert the number history
  at that node to an Integer and add result to the running total.

    def insert_next_node(self, number_history: str = '') -> Union[BinaryTreeNode, None]:
        data = self.node_list[self.index]
        temp_node = None
        if data != self.null_node_char:
            number_history += data
            temp_node = BinaryTreeNode(data)
        self.index += 1

        if temp_node:
            temp_node.left = self.insert_next_node(number_history)
            temp_node.right = self.insert_next_node(number_history)

        if self.node_is_leaf(temp_node):
            self.total_sum += int(number_history)
        return temp_node

• Define Method to Determine Leaf Nodes
  A node is a leaf if it:
  • has no left and right children
  • is not None
    • note, this is b/c in this paradigm we created,
      the None object is not considered a valid node

    @staticmethod
    def node_is_leaf(node: BinaryTreeNode) -> bool:
        if node is None:
            return False
        return (node.left is None) and (node.right is None)

Try Code:

if __name__ == "__main__":
    binary_tree_preorder_data = "6 3 2 ~ ~ 5 7 ~ ~ 4 ~ ~ 5 ~ 4 ~ ~"
    binary_tree_preorder_data = binary_tree_in_order_data.split(' ')
    bt = BinaryTree(binary_tree_preorder_data)
    print("The sum of all root-to-leaf numbers is:", bt.total_sum)

Files

method1.py