Sorted Binary Tree

Question

This is the array I use for BT:

bt_array = [10, 3, 15, 1, None, 9]

This is the code I use currently.

def sorted_array(self): # NEEDS FIX
    # TODO: should return a sorted array
    elements=[]
    if self.left:
        elements += self.left.sorted_array()

    elements.append(self.internal_array)

    if self.right:
        elements += self.right.sorted_array()

    return elements

it returns this:

sorted array [1, 3, None, 10, 9, 15]

but I would like to get it in order smth like this:

 sorted array [None, 1, 3, 9, 10, 15]

Or None can stay where it did, but 9 should be before 10.

The array is not a valid binary tree, that's why u get a wrong result. — SIAJSAJ IJSAIJSAJA
– SIAJSAJ IJSAIJSAJA, Commented Jul 4, 2022 at 22:00

trincot · Accepted Answer · 2022-07-05 07:27:22Z

The input [10, 3, 15, 1, None, 9] describes this tree:

This is not a valid binary search tree. The value 9 should have been a right child of 3. Since the input is wrong, the output cannot be trusted. If such input is expected, you should verify that a tree is a valid BST.

Moreover, this input format is typically used by code challenge sites (e.g. Leet Code), and the None values only serve as stubs to describe the tree unambiguously with a level-order traversal. These None values are not supposed to be included in the output.

If your code produces a list with None values, then it means you created node instances that have an attribute internal_array that is None. Such nodes should not exist in the tree. It is also confusing that this attribute is called that way, as it should certainly not hold an array as value, but a simple number.

Here is some code you could use:

class Node:
    def __init__(self, data=None): 
        self.data = data
        self.left = None
        self.right = None

    @classmethod
    def from_level_order(Node, values):
        dummy = Node()
        queue = [dummy]
        isright = True
        for value in values:
            node = None if value is None else Node(value)
            if isright:
                queue.pop(0).right = node
            else:
                queue[0].left = node
            if node:
                queue.append(node)
            isright = not isright
        return dummy.right                

    def is_bst(self, lower = float('-inf'), upper = float('inf')):
        return (lower <= self.data <= upper
                and (not self.right or self.right.is_bst(self.data, upper))
                and (not self.left or self.left.is_bst(lower, self.data))
        )
    
    def __iter__(self):
        if self.left:
            yield from self.left
        yield self.data
        if self.right:
            yield from self.right

Now for the example input you gave, we can tell that it is not a valid BST with the following code:

tree = Node.from_level_order([10, 3, 15, 1, None, 9])
print(tree.is_bst())  # False

If we correct the input (changing 9 to 11), we can use the above __iter__ method (similar to your function) to get the sorted list:

tree = Node.from_level_order([10, 3, 15, 1, None, 11])
print(tree.is_bst())  # True
print(list(tree))  # [1, 3, 10, 11, 15]

Collectives™ on Stack Overflow

Sorted Binary Tree

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related