Python binary tree use build instead of Node

Question

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
def printPaths(root): 
    path = []
    printPathsRec(root, path, 0)
def printPathsRec(root, path, pathLen):  
    if root is None:
        return
    if(len(path) > pathLen):
        path[pathLen] = root.data
    else:
        path.append(root.data)
    pathLen = pathLen + 1
    if root.left is None and root.right is None:
        printArray(path, pathLen)
    else:
    
        printPathsRec(root.left, path, pathLen)
        printPathsRec(root.right, path, pathLen)

def printArray(ints, len):
    for i in ints[0 : len]:
        print(i," ",end="")
    print()
 

from binarytree import build

values = [7, 3, 2, 6, 9, None, 1, 5, 8]
root = build(values)
print(root) 
printPaths(root.value)
.

I need to build binary tree with build and make the code work, but i can't find out the way. This example is get from internet,they use method like

root = Node(10)
root.left = Node(8)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(5)
root.right.left = Node(2)
printPaths(root)

But i need to use another method to make it happen.

Answer 1

To create binary Tree:

you need a list sequential.

class Node:
    count = 0
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val
        Node.count+= 1
        
    def __str__(self):
        return (f"value is {self.val} \ncount is:{self.count}")
        

If info is given as:

from collections import deque

d = {0:[1,2], 2:[4,5], 1:[3]} # how nodes are connected. key is node number and values is node num of children.

vals = [10,11,12,13,14,15] # values associated with the node num

q = deque()
q.append(0) #<---- root node
li = [vals[0]] #<--- root node val
while(len(q)>0):
    front = q.popleft()
    
    if (d.get(front, 0)):
        if(len(d[front])==2):
            li.append(vals[d[front][0]])
            li.append(vals[d[front][1]])
            q.append(d[front][0])
            q.append(d[front][1])
        else:
            li.append(vals[d[front][0]])
            li.append(None)
            q.append(d[front][0])
#         q.append(d[front][1])
    else:
        li.append(None)
        li.append(None)

This will give you list

li:

[10, 11, 12, 13, None, 14, 15, None, None, None, None, None, None]

---

build:

def build(values):
    if not values:
        return None
    it = iter(values)
    root=Node(next(it))
    q = deque()
    q.append(root)
    while(q):
        front = q.popleft()
        val1 = next(it, None)
        if (val1):
            n1 = Node(val1)
            q.append(n1)
            front.left = n1
            
        val2 = next(it, None)
        if (val2):
            n2 = Node(val2)
            q.append(n2)
            front.right = n2
    return root
    
node = build(li)

---

To print in inorder:

def print_node(root):
    if not root:
        return
    print_node(root.left)
    print(root.val, end=" ")
    print_node(root.right)
   

---

print_node(node)

---

13 11 10 14 12 15

Straight Forward:

from collections import deque

d = {0:[1,2], 2:[4,5], 1:[3]}
vals = [10,11,12,13,14,15]


q = deque()
root = Node(vals[0], 0)
q.append(root)
while(q):
    node = q.popleft()
    if (d.get(node.node_num, {})):
        if(len(d[node.node_num])==2):
            no1 = d[node.node_num][0]
            node.left = Node(vals[no1],no1)
            no2 = d[node.node_num][1]
            node.right = Node(vals[no2], no2)
            q.append(node.left)
            q.append(node.right)
        else:
            no1 = d[node.node_num][0]
            node.left = Node(vals[no1],no1)
            q.append(node.left)

print_node(root)

13 11 10 14 12 15

Added 1 attribute for node_num in class Node