Create a tree using a stack

November 17, 2021

class Node:
    def __init__(self, value):
        self.value = value
        self.leftChild = None
        self.rightChild = None

def createTree(vector):
    # Initialise a stack
    stack = []

    # Initialise a root
    root = Node(vector[0])
    for val in vector[1:]:
        root, stack = addNode(val, stack, root)
    return root

def addNode(x, stack, root):
    while len(stack) != 0 and stack[-1].value < x:
        stack.pop()
    
    node = Node(x)
    if len(stack) == 0:
        node.leftChild = root
        root = node
    else:
        if stack[-1].rightChild is None:
            node.leftChild = stack[-1].rightChild
        stack[-1].rightChild = node
    stack.append(node)
    return root, stack

root = createTree([1, 5, 8, 4, 3, 7, 6, 2])

Expected Result

I am suppose to get this tree with that snippet, but I am not getting it. I am not getting the left child of the node 7. Is that normal? How can I fix that issue?

>Solution :

You are missing a not in this line:

if stack[-1].rightChild is None:

i.e.:

if stack[-1].rightChild is not None:

Your code works fine otherwise (except for the spelling error in .valuer, which would be .value)

In case someone wants to print the tree to validate (because that may be an issue):

def printTree(root):
    print(f'value: {root.value}, '
          f'on the left {root.leftChild.value if root.leftChild else None}, '
          f'on the right {root.rightChild.value if root.rightChild else None}')
    if root.leftChild:
        printTree(root.leftChild)
    if root.rightChild:
        printTree(root.rightChild)

Result:

value: 8, on the left 5, on the right 7
value: 5, on the left 1, on the right None
value: 1, on the left None, on the right None
value: 7, on the left 4, on the right 6
value: 4, on the left None, on the right 3
value: 3, on the left None, on the right None
value: 6, on the left None, on the right 2
value: 2, on the left None, on the right None