Ggthjy

1970s scifi/horror novel where protagonist is used by a crablike creature to feed its larvae, goes mad, and is defeated by retraumatising him

When was drinking water recognized as crucial in marathon running?

How does signal strength relate to bandwidth?

What is better: yes / no radio, or simple checkbox?

Book about a time-travel war fought by computers

Was it really inappropriate to write a pull request for the company I interviewed with?

How can I highlight parts in a screenshot

What is the minimum amount of skill points per HD?

3.5% Interest Student Loan or use all of my savings on Tuition?

It doesn't matter the side you see it

Practical reasons to have both a large police force and bounty hunting network?

Reason why dimensional travelling would be restricted

Being asked to review a paper in conference one has submitted to

Do AL rules let me pick different starting equipment?

How do I deal with being envious of my own players?

Can I solder 12/2 Romex to extend wire 5 ft?

Rationale to prefer local variables over instance variables?

Split a number into equal parts given the number of parts

How do you say “my friend is throwing a party, do you wanna come?” in german

Plagiarism of code by other PhD student

Relationship between the symmetry number of a molecule as used in rotational spectroscopy and point group

I encountered my boss during an on-site interview at another company. Should I bring it up when seeing him next time?

Is there a way to find out the age of climbing ropes?

The need of reserving one's ability in job interviews

Building balanced BST from sorted array: recursive and iterative approaches

Knapsack branch and bound: forward filterAutocomplete Trie OptimizationRecursive and iterative approach for mergesortSearch iteratively in a ternary search treeFind kth largest element in the union of two sorted array (Follow up)Bytecode Interpreter for a custom programming languageCount of Smaller Numbers After SelfPalindrome implementations - iterative and recursiveSubtract first and last nodes of linked listFind maximum in sorted and rotated array

0

$begingroup$

I am implementing an algorithm to solve the following problem:

Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

The solution of this problem using recursion is quite straightforward:

class Node:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None





def build_bst_recursive(array):

    size = len(array)

    return _build_bst(array, first=0, last=size - 1)





def _build_bst(array, first, last):

    if last < first:

        return None

    mid = (first + last) // 2

    node = Node(mid)

    node.left = _build_bst(array, first, mid - 1)

    node.right = _build_bst(array, mid + 1, last)

    return node

Out of curiosity I also would like to solve the same problem using an iterative algorithm. Here is what I came up with:

class Stack:

    class _Node:

        def __init__(self, value):

            self.value = value

            self.next_node = None



    def __init__(self):

        self.head_node = None



    def is_empty(self):

        return self.head_node is None



    def push(self, value):

        node = self._Node(value)

        node.next_node = self.head_node

        self.head_node = node



    def pop(self):

        if self.is_empty():

            raise Exception("Stack is empty.")

        node = self.head_node

        self.head_node = node.next_node

        return node.value



def build_bst_iterative(array):

    size = len(array)



    stack_indices = Stack()

    stack_indices.push((0, size - 1))



    stack_nodes = Stack()

    root_node = Node(None)

    stack_nodes.push(root_node)



    while not stack_indices.is_empty():

        first, last = stack_indices.pop()

        node = stack_nodes.pop()



        if last == first:

            node.value = array[last]

            node.left = None

            node.right = None

            continue



        mid = (first + last) // 2

        node.value = array[mid]

        node.left = Node(None)

        node.right = Node(None)



        stack_indices.push((mid + 1, last))

        stack_nodes.push(node.right)



        stack_indices.push((first, mid - 1))

        stack_nodes.push(node.left)

    assert stack_nodes.is_empty()



    return root_node

I would highly appreciate if you could review the code and suggest any approaches for improvement. For example, I am trying to understand if it is possible to use only one stack.

python binary-search

share

asked 5 mins ago

desadesa

101

New contributor

desa is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

0

$begingroup$

I am implementing an algorithm to solve the following problem:

Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

The solution of this problem using recursion is quite straightforward:

class Node:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None





def build_bst_recursive(array):

    size = len(array)

    return _build_bst(array, first=0, last=size - 1)





def _build_bst(array, first, last):

    if last < first:

        return None

    mid = (first + last) // 2

    node = Node(mid)

    node.left = _build_bst(array, first, mid - 1)

    node.right = _build_bst(array, mid + 1, last)

    return node

Out of curiosity I also would like to solve the same problem using an iterative algorithm. Here is what I came up with:

class Stack:

    class _Node:

        def __init__(self, value):

            self.value = value

            self.next_node = None



    def __init__(self):

        self.head_node = None



    def is_empty(self):

        return self.head_node is None



    def push(self, value):

        node = self._Node(value)

        node.next_node = self.head_node

        self.head_node = node



    def pop(self):

        if self.is_empty():

            raise Exception("Stack is empty.")

        node = self.head_node

        self.head_node = node.next_node

        return node.value



def build_bst_iterative(array):

    size = len(array)



    stack_indices = Stack()

    stack_indices.push((0, size - 1))



    stack_nodes = Stack()

    root_node = Node(None)

    stack_nodes.push(root_node)



    while not stack_indices.is_empty():

        first, last = stack_indices.pop()

        node = stack_nodes.pop()



        if last == first:

            node.value = array[last]

            node.left = None

            node.right = None

            continue



        mid = (first + last) // 2

        node.value = array[mid]

        node.left = Node(None)

        node.right = Node(None)



        stack_indices.push((mid + 1, last))

        stack_nodes.push(node.right)



        stack_indices.push((first, mid - 1))

        stack_nodes.push(node.left)

    assert stack_nodes.is_empty()



    return root_node

I would highly appreciate if you could review the code and suggest any approaches for improvement. For example, I am trying to understand if it is possible to use only one stack.

python binary-search

share

asked 5 mins ago

desadesa

101

New contributor

desa is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

I am implementing an algorithm to solve the following problem:

Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

The solution of this problem using recursion is quite straightforward:

class Node:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None





def build_bst_recursive(array):

    size = len(array)

    return _build_bst(array, first=0, last=size - 1)





def _build_bst(array, first, last):

    if last < first:

        return None

    mid = (first + last) // 2

    node = Node(mid)

    node.left = _build_bst(array, first, mid - 1)

    node.right = _build_bst(array, mid + 1, last)

    return node

Out of curiosity I also would like to solve the same problem using an iterative algorithm. Here is what I came up with:

class Stack:

    class _Node:

        def __init__(self, value):

            self.value = value

            self.next_node = None



    def __init__(self):

        self.head_node = None



    def is_empty(self):

        return self.head_node is None



    def push(self, value):

        node = self._Node(value)

        node.next_node = self.head_node

        self.head_node = node



    def pop(self):

        if self.is_empty():

            raise Exception("Stack is empty.")

        node = self.head_node

        self.head_node = node.next_node

        return node.value



def build_bst_iterative(array):

    size = len(array)



    stack_indices = Stack()

    stack_indices.push((0, size - 1))



    stack_nodes = Stack()

    root_node = Node(None)

    stack_nodes.push(root_node)



    while not stack_indices.is_empty():

        first, last = stack_indices.pop()

        node = stack_nodes.pop()



        if last == first:

            node.value = array[last]

            node.left = None

            node.right = None

            continue



        mid = (first + last) // 2

        node.value = array[mid]

        node.left = Node(None)

        node.right = Node(None)



        stack_indices.push((mid + 1, last))

        stack_nodes.push(node.right)



        stack_indices.push((first, mid - 1))

        stack_nodes.push(node.left)

    assert stack_nodes.is_empty()



    return root_node

I would highly appreciate if you could review the code and suggest any approaches for improvement. For example, I am trying to understand if it is possible to use only one stack.

python binary-search

share

asked 5 mins ago

desadesa

101

New contributor

desa is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

class Node:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None





def build_bst_recursive(array):

    size = len(array)

    return _build_bst(array, first=0, last=size - 1)





def _build_bst(array, first, last):

    if last < first:

        return None

    mid = (first + last) // 2

    node = Node(mid)

    node.left = _build_bst(array, first, mid - 1)

    node.right = _build_bst(array, mid + 1, last)

    return node

class Stack:

    class _Node:

        def __init__(self, value):

            self.value = value

            self.next_node = None



    def __init__(self):

        self.head_node = None



    def is_empty(self):

        return self.head_node is None



    def push(self, value):

        node = self._Node(value)

        node.next_node = self.head_node

        self.head_node = node



    def pop(self):

        if self.is_empty():

            raise Exception("Stack is empty.")

        node = self.head_node

        self.head_node = node.next_node

        return node.value



def build_bst_iterative(array):

    size = len(array)



    stack_indices = Stack()

    stack_indices.push((0, size - 1))



    stack_nodes = Stack()

    root_node = Node(None)

    stack_nodes.push(root_node)



    while not stack_indices.is_empty():

        first, last = stack_indices.pop()

        node = stack_nodes.pop()



        if last == first:

            node.value = array[last]

            node.left = None

            node.right = None

            continue



        mid = (first + last) // 2

        node.value = array[mid]

        node.left = Node(None)

        node.right = Node(None)



        stack_indices.push((mid + 1, last))

        stack_nodes.push(node.right)



        stack_indices.push((first, mid - 1))

        stack_nodes.push(node.left)

    assert stack_nodes.is_empty()



    return root_node

share

asked 5 mins ago

desadesa

101

New contributor

desa is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share

asked 5 mins ago

desadesa

101

New contributor

desa is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 5 mins ago

desadesa

101

New contributor

desa is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 5 mins ago

desadesa

101