1 of 4

Binary Search Tree

class BSTNode:
    def __init__(self,

The following is the definition of Binary Search Tree(BST) according to Binary Search Tree is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.

The above properties of Binary Search Tree provides an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search for a given key.

Searching a key For searching a value, if we had a sorted array we could have performed a binary search. Let’s say we want to search a number in the array what we do in binary search is we first define the complete list as our search space, the number can exist only within the search space. Now we compare the number to be searched or the element to be searched with the mid element of the search space or the median and if the record being searched is lesser we go searching in the left half else we go searching in the right half, in case of equality we have found the element. In binary search we start with ‘n’ elements in search space and then if the mid element is not the element that we are looking for, we reduce the search space to ‘n/2’ and we go on reducing the search space till we either find the record that we are looking for or we get to only one element in search space and be done with this whole reduction. Search operation in binary search tree will be very similar. Let’s say we want to search for the number, what we’ll do is we’ll start at the root, and then we will compare the value to be searched with the value of the root if it’s equal we are done with the search if it’s lesser we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are lesser and all the elements in the right subtree are greater. Searching an element in the binary search tree is basically this traversal in which at each step we will go either towards left or right and hence in at each step we discard one of the sub-trees. If the tree is balanced, we call a tree balanced if for all nodes the difference between the heights of left and right subtrees is not greater than one, we will start with a search space of ‘n’nodes and when we will discard one of the sub-trees we will discard ‘n/2’ nodes so our search space will be reduced to ‘n/2’ and then in the next step we will reduce the search space to ‘n/4’ and we will go on reducing like this till we find the element or till our search space is reduced to only one node. The search here is also a binary search and that’s why the name binary search tree.

Illustration to search 6 in below tree: 1. Start from the root. 2. Compare the searching element with root, if less than root, then recurse for left, else recurse for right. 3. If the element to search is found anywhere, return true, else return false.

Insertion of a key A new key is always inserted at the leaf. We start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

Output

Illustration to insert 2 in below tree: 1. Start from the root. 2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right. 3. After reaching the end, just insert that node at left(if less than current) else right.

Time Complexity: The worst-case time complexity of search and insert operations is O(h) where h is the height of the Binary Search Tree. In the worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).

Insertion using loop:

Output

Some Interesting Facts:

Inorder traversal of BST always produces sorted output.
We can construct a BST with only Preorder or Postorder or Level Order traversal. Note that we can always get inorder traversal by sorting the only given traversal.

Related Links:

BST

Pros of a BST

When balanced, a BST provides lightning-fast O(log(n)) insertions, deletions, and lookups.
Binary search trees are pretty simple. An ordinary BST, unlike a balanced tree like a red-black tree, requires very little code to get running.

Cons of a BST

Slow for a brute-force search. If you need to iterate over each node, you might have more success with an array.
When the tree becomes unbalanced, all fast O(log(n)) operations quickly degrade to O(n).
Since pointers to whole objects are typically involved, a BST can require quite a bit more memory than an array, although this depends on the implementation.

Implementing a BST in Python

Step 1 – BSTNode Class

Our implementation won’t use a Tree class, but instead just a Node class. Binary trees are really just a pointer to a root node that in turn connects to each child node, so we’ll run with that idea.

First, we create a constructor:

We’ll allow a value (key) to be provided, but if one isn’t provided we’ll just set it to None. We’ll also initialize both children of the new node to None.

Step 2 – Insert

We need a way to insert new data. The insert method is as follows:

If the node doesn’t yet have a value, we can just set the given value and return. If we ever try to insert a value that also exists, we can also simply return as this can be considered a noop. If the given value is less than our node’s value and we already have a left child then we recursively call insert on our left child. If we don’t have a left child yet then we just make the given value our new left child. We can do the same (but inverted) for our right side.

Step 3 – Get Min and Get Max

getMin and getMax are useful helper functions, and they’re easy to write! They are simple recursive functions that traverse the edges of the tree to find the smallest or largest values stored therein.

Step 4 – Delete

The delete operation is one of the more complex ones. It is a recursive function as well, but it also returns the new state of the given node after performing the delete operation. This allows a parent whose child has been deleted to properly set it’s left or right data member to None.

Step 5 – Exists

The exists function is another simple recursive function that returns True or False depending on whether a given value already exists in the tree.

Step 6 – Inorder

It’s useful to be able to print out the tree in a readable format. The inorder method print’s the values in the tree in the order of their keys.

Step 7 – Preorder

Step 8 – Postorder

Using the BST

Full Binary Search Tree in Python

Where would you use a binary search tree in real life?

There are many applications of binary search trees in real life, and one of the most common use-cases is in storing indexes and keys in a database. For example, in MySQL or PostgresQL when you create a primary key column, what you’re really doing is creating a binary tree where the keys are the values of the column, and those nodes point to database rows. This lets the application easily search database rows by providing a key. For example, getting a user record by the email primary key.

There are many applications of binary search trees in real life, and one of the most common use cases is storing indexes and keys in a database. For example, when you create a primary key column in MySQL or PostgresQL, you create a binary tree where the keys are the values of the column and the nodes point to database rows. This allows the application to easily search for database rows by specifying a key, for example, to find a user record using the email primary key.

Other common uses include:

Pathfinding algorithms in videogames (A*) use BSTs
File compression using a Huffman encoding scheme uses a binary search tree
Rendering calculations – Doom (1993) was famously the first game to use a BST

Example Binary Tree

Visual Aid

Example Code

Terms

tree - graph with no cycles
binary tree - tree where nodes have at most 2 nodes
root - the ultimate parent, the single node of a tree that can access every other node through edges; by definition the root will not have a parent

Search Patterns

Breadth First Search - Check all nodes at a level before moving down a level
- Think of this of searching horizontally in rows
Depth First Search - Check the depth as far as it goes for one child, before

Constraints

Binary trees have at most two children per node
Given any node of the tree, the values on the left must be strictly less than that node
Given any node of the tree, the values on the right must be strictly greater than or equal to that node

PseudoCode For Insertion

Create a new node
Start at the root
- Check if there is a root

PseudoCode For Search Of A single Item

Start at the root
- Check if there is a root
  - If not, there is nothing in the tree, so the search is over

PseudoCode For Breadth First Search Traversal

Create a queue class or use an array
Create a variable to store the values of the nodes visited
Place the root in the queue

PseudoCode For Depth First Search Traversal

Pre-Order

Iterative

Create a stack class or use an array
Push the root into the stack
Create a variable to store the values of the nodes visited

Recursive

Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property

In-Order

Iterative

Create a stack class or use an array
Create a variable to store the current root
Create a variable to store the values of the nodes visited

Recursive

Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property

Post-Order

Iterative

Haven't figured this one out yet.

Recursive

Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property

Example Binary Search Tree

BST Explained

What is a Binary Search Tree?

Binary Search Tree is a kind of tree in which each node follows specific properties to construct a tree.

BST Insert

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def binary_insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                binary_insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                binary_insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)

r = Node(3)
binary_insert(r, Node(7))
binary_insert(r, Node(1))
binary_insert(r, Node(5))

BST-Largest-Sub-Tree

Binary Search Tree

class BSTNode:
    def __init__(self,

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        # create a node for the new value
        new_node = BSTNode(value)
        # compare the node value to the self value
        if (
            new_node.value <= self.value
        ):  # less then or equal to will all go to the left if any duplicats too
            # we add to the left
            if self.left is None:
                self.left = new_node
            else:
                self.left.insert(value)
        else:
            # we add to the right
            # if space exists
            if self.right is None:
                self.right = new_node
            else:
                self.right.insert(value)

    def search(self, target):
        if target == self.value:
            return True
        # check if value is less than self.value

        if target < self.value:
            # look to the left
            if self.left is None:
                return False
            return self.left.search(target)

        else:
            # look to the right
            if self.right is None:
                return False
            return self.right.search(target)

    def find_minimum_value(self):
        # if self.left is None: #recursive here
        #     return self.value
        # min_value =  self.left.find_minimum_value()
        # return min_value
        curr_node = self
        while curr_node.left is not None:
            curr_node = curr_node.left
        return curr_node.value


root = BSTNode(10)
# root.left = BSTNode(6)
# root.right = BSTNode(12)
root.insert(6)
root.insert(7)
root.insert(12)
root.insert(5)
root.insert(14)
root.insert(8)

print(f"minimum value in tree is: {root.find_minimum_value()}")

print(f"does 8 exist? {root.search(8)}")
print(f"does 8 exist? {root.search(7)}")
print(f"does 8 exist? {root.search(15)}")class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        # create a node for the new value
        new_node = BSTNode(value)
        # compare the node value to the self value
        if (
            new_node.value <= self.value
        ):  # less then or equal to will all go to the left if any duplicats too
            # we add to the left
            if self.left is None:
                self.left = new_node
            else:
                self.left.insert(value)
        else:
            # we add to the right
            # if space exists
            if self.right is None:
                self.right = new_node
            else:
                self.right.insert(value)

    def search(self, target):
        if target == self.value:
            return True
        # check if value is less than self.value

        if target < self.value:
            # look to the left
            if self.left is None:
                return False
            return self.left.search(target)

        else:
            # look to the right
            if self.right is None:
                return False
            return self.right.search(target)

    def find_minimum_value(self):
        # if self.left is None: #recursive here
        #     return self.value
        # min_value =  self.left.find_minimum_value()
        # return min_value
        curr_node = self
        while curr_node.left is not None:
            curr_node = curr_node.left
        return curr_node.value


root = BSTNode(10)
# root.left = BSTNode(6)
# root.right = BSTNode(12)
root.insert(6)
root.insert(7)
root.insert(12)
root.insert(5)
root.insert(14)
root.insert(8)

print(f"minimum value in tree is: {root.find_minimum_value()}")

print(f"does 8 exist? {root.search(8)}")
print(f"does 8 exist? {root.search(7)}")
print(f"does 8 exist? {root.search(15)}")

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        # create a node for the new value
        new_node = BSTNode(value)
        # compare the node value to the self value
        if (
            new_node.value <= self.value
        ):  # less then or equal to will all go to the left if any duplicats too
            # we add to the left
            if self.left is None:
                self.left = new_node
            else:
                self.left.insert(value)
        else:
            # we add to the right
            # if space exists
            if self.right is None:
                self.right = new_node
            else:
                self.right.insert(value)

    def search(self, target):
        if target == self.value:
            return True
        # check if value is less than self.value

        if target < self.value:
            # look to the left
            if self.left is None:
                return False
            return self.left.search(target)

        else:
            # look to the right
            if self.right is None:
                return False
            return self.right.search(target)

    def find_minimum_value(self):
        # if self.left is None: #recursive here
        #     return self.value
        # min_value =  self.left.find_minimum_value()
        # return min_value
        curr_node = self
        while curr_node.left is not None:
            curr_node = curr_node.left
        return curr_node.value


root = BSTNode(10)
# root.left = BSTNode(6)
# root.right = BSTNode(12)
root.insert(6)
root.insert(7)
root.insert(12)
root.insert(5)
root.insert(14)
root.insert(8)

print(f"minimum value in tree is: {root.find_minimum_value()}")

print(f"does 8 exist? {root.search(8)}")
print(f"does 8 exist? {root.search(7)}")
print(f"does 8 exist? {root.search(15)}")

# Implement a Binary Search Tree (BST) that can insert values and check if
# values are present

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

class BST(object):
    def __init__(self, root):
        self.root = Node(root)

    def insert(self, new_val):
        if(self.root.left==None):
            if(self.root.value>new_val):
                self.root.left = Node(new_val)
        elif(self.root.right==None):
            if(self.root.value<new_val):
                self.root.right = Node(new_val)
        else:
            current = self.root
            while(current.left!=None or current.right!=None):
                if(current.value>new_val):
                    current = current.left
                else:
                    current = current.right

            if(current.left==None):
                current.left = Node(new_val)
            else:
                current.right = Node(new_val)

    def search(self, find_val):
        if(self.root.left==None and self.root.right==None and self.root.value!=find_val):
            return False
        else:
            current = self.root
            val_possible = True
            while(val_possible):
                if(current.value==find_val):
                        return True
                if(current.value<find_val):
                    current = current.right
                else:
                    current = current.left
                if(current==None):
                    return False
                if(current.value<find_val and (current.right==None or current.right>find_val)):
                    return False
                if(current.value>find_val and (current.left==None or current.left<find_val)):
                    return False

# Set up tree
tree = BST(4)

# Insert elements
tree.insert(2)
tree.insert(1)
tree.insert(3)
tree.insert(5)

# Check search
# Should be True
print tree.search(4)
# Should be False
print tree.search(6)

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

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def preorder_search(self, start, find_val):
        """Helper method - use this to create a
        recursive search solution."""
        if(start.value == find_val):
            return True
        if(start.left!=None):
            left_result = self.preorder_search(start.left, find_val)
        else:
            left_result = False
        if(start.right!=None and left_result!=True):
            right_result = self.preorder_search(start.right, find_val)
        else:
            right_result = False

        if(left_result==True or right_result==True):
            return True
        else:
            return False

    def preorder_print(self, start, traversal):
        """Helper method - use this to create a
        recursive print solution."""
        traversal += '-' + str(start.value)
        left_nums = ''
        right_nums = ''
        if(start.left!=None):
            traversal = self.preorder_print(start.left, traversal)
        if(start.right!=None):
            traversal = self.preorder_print(start.right, traversal)
        return traversal

    def search(self, find_val):
        """Return True if the value
        is in the tree, return
        False otherwise."""
        return self.preorder_search(self.root, find_val)
        #print(self.preorder_search(self.root, find_val))

    def print_tree(self):
        """Print out all tree nodes
        as they are visited in
        a pre-order traversal."""
        all_nodes = self.preorder_print(self.root, '')
        all_nodes = all_nodes[1:]
        return all_nodes


# Set up tree
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

# Test search
# Should be True
print(tree.search(4))
# Should be False
print(tree.search(6))

# Test print_tree
# Should be 1-2-4-5-3
print(tree.print_tree())

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        # create a node for the new value
        new_node = BSTNode(value)
        # compare the node value to the self value
        if (
            new_node.value <= self.value
        ):  # less then or equal to will all go to the left if any duplicats too
            # we add to the left
            if self.left is None:
                self.left = new_node
            else:
                self.left.insert(value)
        else:
            # we add to the right
            # if space exists
            if self.right is None:
                self.right = new_node
            else:
                self.right.insert(value)

    def search(self, target):
        if target == self.value:
            return True
        # check if value is less than self.value

        if target < self.value:
            # look to the left
            if self.left is None:
                return False
            return self.left.search(target)

        else:
            # look to the right
            if self.right is None:
                return False
            return self.right.search(target)

    def find_minimum_value(self):
        # if self.left is None: #recursive here
        #     return self.value
        # min_value =  self.left.find_minimum_value()
        # return min_value
        curr_node = self
        while curr_node.left is not None:
            curr_node = curr_node.left
        return curr_node.value


root = BSTNode(10)
# root.left = BSTNode(6)
# root.right = BSTNode(12)
root.insert(6)
root.insert(7)
root.insert(12)
root.insert(5)
root.insert(14)
root.insert(8)

print(f"minimum value in tree is: {root.find_minimum_value()}")

print(f"does 8 exist? {root.search(8)}")
print(f"does 8 exist? {root.search(7)}")
print(f"does 8 exist? {root.search(15)}")

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
class BST:
    def __init__(self):
        self.root = None
    def Insert(self, value):
        self.root = self.__InsertWrap(self.root, value)
    def __InsertWrap(self, x, value):
        if x == None:
            x = Node(value)
        else:
            if value < x.value:
                # print("left")
                x.left = self.__InsertWrap(x.left, value)
            else:
                # print("right")
                x.right = self.__InsertWrap(x.right, value)
        return x
    def InOrder(self):
        return self.__InOrder(self.root)
    def __InOrder(self, x):
        if x:
            self.__InOrder(x.left)
            print(x.value)
            self.__InOrder(x.right)
    def PreOrder(self):
        return self.__PreOrder(self.root)
    def __PreOrder(self, x):
        if x:
            print(x.value)
            self.__PreOrder(x.left)
            self.__PreOrder(x.right)
    def PostOrder(self):
        return self.__PostOrder(self.root)
    def __PostOrder(self, x):
        if x:
            self.__PostOrder(x.left)
            self.__PostOrder(x.right)
            print(x.value)
    def FindMin(self, x):
        while x.left != None:
            x = x.left
        return x.value
    def FindMax(self, x):
        while x.right != None:
            x = x.right
        return x.value
    def successor(self, x):
        if x.right != None:
            xx = x.right
            while xx.left != None:
                xx = xx.left
        return xx.value
    def predecessor(self, x):
        if x.left != None:
            xx = x.left
            while xx.right != None:
                xx = x.right
        return xx.value
    def Height(self, x):
        y = self.__Height(x)
        return y
    def __Height(self, x):
        if x == None:
            return 0
        else:
            return 1 + max(self.__Height(x.left), self.__Height(x.right))
    def delete(self, node):
        x = self.root  # rootNode, {Parent Node of desired Node}
        if node > x.value:
            y = x.right  # desiredNode {Node to be delted} [iff on right]
        else:
            y = x.left  # desiredNode [iff left]
        while y.value != node:  # Searching the Node to delete
            if node > y.value:
                x = x.right
                y = y.right
            else:
                x = x.left
                y = y.left
        # print("xr", x.right.value)
        # print("y", y.value)
        left = x.left  # left of ParentNode
        right = x.right  # right of ParentNode
        # Case 01
        if left.value == y.value and left.left is None and left.right is None:
            # print("left", x.left.value)
            x.left = None
        elif right.value == y.value and right.left is None and right.right is None:
            # print("right", x.right.value)
            x.right = None
        # Case 02
        elif (
            left.value == y.value
            and (left.left is not None and left.right is None)
            or (left.left is None and left.right is not None)
        ):
            if left.left is not None:
                child = left.left
            elif left.right is not None:
                child = left.right
            x.left = None
            x.left = child
            # print("x",x.left.value)
        elif (
            right.value == y.value
            and (right.left is not None and right.right is None)
            or (right.left is None and right.right is not None)
        ):
            if right.left is not None:
                child = right.left
            elif right.right is not None:
                child = right.right
            x.right = None
            x.right = child
        # Case 03
        elif left.value == y.value and left.left is not None and left.right is not None:
            lChild = left.left
            rChild = left.right
            min = self.successor(left)
            self.delete(min)
            minNode = Node(min)
            minNode.left = lChild
            minNode.right = rChild
            x.left = None
            x.left = minNode
        elif (
            right.value == y.value
            and right.left is not None
            and right.right is not None
        ):
            lChild = right.left
            rChild = right.right
            min = self.successor(right)
            self.delete(min)
            minNode = Node(min)
            minNode.left = lChild
            minNode.right = rChild
            x.right = None
            x.right = minNode
# Driver Code
a = BST()
a.Insert(20)
a.Insert(40)
a.Insert(12)
a.Insert(1)
root = a.root
print("Getting Inorder:")
a.InOrder()
print("\nGetting Preorder:")
a.PreOrder()
print("\nGetting PostOrder:")
a.PostOrder()
print("\nGetting Height:")
print(a.Height(root))
print("\nGetting Minimum Node:")
print(a.FindMin(root))
print("\nGetting Maximum Node:")
print(a.FindMax(root))
print("\nGetting Successor:")
print(a.successor(root))
print("\nGetting Predecessor:")
print(a.predecessor(root))
print("\nDeleting a specific Node:")
a.delete(12)
print("\nTo cross-check deletion, printing preorder:")
a.PreOrder()
# In[ ]:

The following is the definition of Binary Search Tree(BST) according to Binary Search Tree is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.

Output

Insertion using loop:

Output

Some Interesting Facts:

Inorder traversal of BST always produces sorted output.
We can construct a BST with only Preorder or Postorder or Level Order traversal. Note that we can always get inorder traversal by sorting the only given traversal.

Related Links:

BST

Pros of a BST

When balanced, a BST provides lightning-fast O(log(n)) insertions, deletions, and lookups.
Binary search trees are pretty simple. An ordinary BST, unlike a balanced tree like a red-black tree, requires very little code to get running.

Cons of a BST

Slow for a brute-force search. If you need to iterate over each node, you might have more success with an array.
When the tree becomes unbalanced, all fast O(log(n)) operations quickly degrade to O(n).
Since pointers to whole objects are typically involved, a BST can require quite a bit more memory than an array, although this depends on the implementation.

Implementing a BST in Python

Step 1 – BSTNode Class

First, we create a constructor:

We’ll allow a value (key) to be provided, but if one isn’t provided we’ll just set it to None. We’ll also initialize both children of the new node to None.

Step 2 – Insert

We need a way to insert new data. The insert method is as follows:

Step 3 – Get Min and Get Max

Step 4 – Delete

Step 5 – Exists

The exists function is another simple recursive function that returns True or False depending on whether a given value already exists in the tree.

Step 6 – Inorder

It’s useful to be able to print out the tree in a readable format. The inorder method print’s the values in the tree in the order of their keys.

Step 7 – Preorder

Step 8 – Postorder

Using the BST

Full Binary Search Tree in Python

Where would you use a binary search tree in real life?

Other common uses include:

Pathfinding algorithms in videogames (A*) use BSTs
File compression using a Huffman encoding scheme uses a binary search tree
Rendering calculations – Doom (1993) was famously the first game to use a BST

Example Binary Tree

Visual Aid

Example Code

Terms

tree - graph with no cycles
binary tree - tree where nodes have at most 2 nodes
root - the ultimate parent, the single node of a tree that can access every other node through edges; by definition the root will not have a parent

Search Patterns

Breadth First Search - Check all nodes at a level before moving down a level
- Think of this of searching horizontally in rows
Depth First Search - Check the depth as far as it goes for one child, before

Constraints

Binary trees have at most two children per node
Given any node of the tree, the values on the left must be strictly less than that node
Given any node of the tree, the values on the right must be strictly greater than or equal to that node

PseudoCode For Insertion

Create a new node
Start at the root
- Check if there is a root

PseudoCode For Search Of A single Item

Start at the root
- Check if there is a root
  - If not, there is nothing in the tree, so the search is over

PseudoCode For Breadth First Search Traversal

Create a queue class or use an array
Create a variable to store the values of the nodes visited
Place the root in the queue

PseudoCode For Depth First Search Traversal

Pre-Order

Iterative

Create a stack class or use an array
Push the root into the stack
Create a variable to store the values of the nodes visited

Recursive

Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property

In-Order

Iterative

Create a stack class or use an array
Create a variable to store the current root
Create a variable to store the values of the nodes visited

Recursive

Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property

Post-Order

Iterative

Haven't figured this one out yet.

Recursive

Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property

Example Binary Search Tree

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
class BST:
    def __init__(self):
        self.root = None
    def Insert(self, value):
        self.root = self.__InsertWrap(self.root, value)
    def __InsertWrap(self, x, value):
        if x == None:
            x = Node(value)
        else:
            if value < x.value:
                # print("left")
                x.left = self.__InsertWrap(x.left, value)
            else:
                # print("right")
                x.right = self.__InsertWrap(x.right, value)
        return x
    def InOrder(self):
        return self.__InOrder(self.root)
    def __InOrder(self, x):
        if x:
            self.__InOrder(x.left)
            print(x.value)
            self.__InOrder(x.right)
    def PreOrder(self):
        return self.__PreOrder(self.root)
    def __PreOrder(self, x):
        if x:
            print(x.value)
            self.__PreOrder(x.left)
            self.__PreOrder(x.right)
    def PostOrder(self):
        return self.__PostOrder(self.root)
    def __PostOrder(self, x):
        if x:
            self.__PostOrder(x.left)
            self.__PostOrder(x.right)
            print(x.value)
    def FindMin(self, x):
        while x.left != None:
            x = x.left
        return x.value
    def FindMax(self, x):
        while x.right != None:
            x = x.right
        return x.value
    def successor(self, x):
        if x.right != None:
            xx = x.right
            while xx.left != None:
                xx = xx.left
        return xx.value
    def predecessor(self, x):
        if x.left != None:
            xx = x.left
            while xx.right != None:
                xx = x.right
        return xx.value
    def Height(self, x):
        y = self.__Height(x)
        return y
    def __Height(self, x):
        if x == None:
            return 0
        else:
            return 1 + max(self.__Height(x.left), self.__Height(x.right))
    def delete(self, node):
        x = self.root  # rootNode, {Parent Node of desired Node}
        if node > x.value:
            y = x.right  # desiredNode {Node to be delted} [iff on right]
        else:
            y = x.left  # desiredNode [iff left]
        while y.value != node:  # Searching the Node to delete
            if node > y.value:
                x = x.right
                y = y.right
            else:
                x = x.left
                y = y.left
        # print("xr", x.right.value)
        # print("y", y.value)
        left = x.left  # left of ParentNode
        right = x.right  # right of ParentNode
        # Case 01
        if left.value == y.value and left.left is None and left.right is None:
            # print("left", x.left.value)
            x.left = None
        elif right.value == y.value and right.left is None and right.right is None:
            # print("right", x.right.value)
            x.right = None
        # Case 02
        elif (
            left.value == y.value
            and (left.left is not None and left.right is None)
            or (left.left is None and left.right is not None)
        ):
            if left.left is not None:
                child = left.left
            elif left.right is not None:
                child = left.right
            x.left = None
            x.left = child
            # print("x",x.left.value)
        elif (
            right.value == y.value
            and (right.left is not None and right.right is None)
            or (right.left is None and right.right is not None)
        ):
            if right.left is not None:
                child = right.left
            elif right.right is not None:
                child = right.right
            x.right = None
            x.right = child
        # Case 03
        elif left.value == y.value and left.left is not None and left.right is not None:
            lChild = left.left
            rChild = left.right
            min = self.successor(left)
            self.delete(min)
            minNode = Node(min)
            minNode.left = lChild
            minNode.right = rChild
            x.left = None
            x.left = minNode
        elif (
            right.value == y.value
            and right.left is not None
            and right.right is not None
        ):
            lChild = right.left
            rChild = right.right
            min = self.successor(right)
            self.delete(min)
            minNode = Node(min)
            minNode.left = lChild
            minNode.right = rChild
            x.right = None
            x.right = minNode
# Driver Code
a = BST()
a.Insert(20)
a.Insert(40)
a.Insert(12)
a.Insert(1)
root = a.root
print("Getting Inorder:")
a.InOrder()
print("\nGetting Preorder:")
a.PreOrder()
print("\nGetting PostOrder:")
a.PostOrder()
print("\nGetting Height:")
print(a.Height(root))
print("\nGetting Minimum Node:")
print(a.FindMin(root))
print("\nGetting Maximum Node:")
print(a.FindMax(root))
print("\nGetting Successor:")
print(a.successor(root))
print("\nGetting Predecessor:")
print(a.predecessor(root))
print("\nDeleting a specific Node:")
a.delete(12)
print("\nTo cross-check deletion, printing preorder:")
a.PreOrder()
# In[ ]:

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  //Insert a new node

  recursiveInsert(val, currentNode = this.root) {
    if (!this.root) {
      this.root = new TreeNode(val);
      return this;
    }
    if (val < currentNode.val) {
      if (!currentNode.left) {
        currentNode.left = new TreeNode(val);
      } else {
        this.insert(val, currentNode.left);
      }
    } else {
      if (!currentNode.right) {
        currentNode.right = new TreeNode(val);
      } else {
        this.insert(val, currentNode.right);
      }
    }
  }

  iterativeInsert(val, currentNode = this.root) {
    if (!this.root) {
      this.root = new TreeNode(val);
      return this;
    }
    if (val < currentNode.val) {
      if (!currentNode.left) {
        currentNode.left = new TreeNode();
      } else {
        while (true) {
          if (val < currentNode.val) {
            if (!currenNodet.left) {
              currentNode.left = new TreeNode();
              return this;
            } else {
              currentNode = currentNode.left;
            }
          } else {
            if (!currentNode.right) {
              currentNode.right = new TreeNode();
              return this;
            } else {
              currentNode = currentNode.right;
            }
          }
        }
      }
    }
  }

  //Search the tree

  searchRecur(val, currentNode = this.root) {
    if (!currentNode) return false;
    if (val < currentNode.val) {
      return this.searchRecur(val, currentNode.left);
    } else if (val > currentNode.val) {
      return this.searchRecur(val, currentNode.right);
    } else {
      return true;
    }
  }

  searchIter(val) {
    let currentNode = this.root;
    while (currentNode) {
      if (val < currentNode.val) {
        currentNode = currentNode.left;
      } else if (val > currentNode.val) {
        currentNode = currentNode.right;
      } else {
        return true;
      }
    }
    return false;
  }

  // Maybe works, who knows, pulled it off the internet....

  deleteNodeHelper(root, key) {
    if (root === null) {
      return false;
    }
    if (key < root.val) {
      root.left = deleteNodeHelper(root.left, key);
      return root;
    } else if (key > root.val) {
      root.right = deleteNodeHelper(root.right, key);
      return root;
    } else {
      if (root.left === null && root.right === null) {
        root = null;
        return root;
      }
      if (root.left === null) return root.right;
      if (root.right === null) return root.left;

      let currNode = root.right;
      while (currNode.left !== null) {
        currNode = currNode.left;
      }
      root.val = currNode.val;
      root.right = deleteNodeHelper(root.right, currNode.val);
      return root;
    }
  }

  //Recursive Depth First Search

  preOrderTraversal(root) {
    if (!root) return [];
    let left = this.preOrderTraversal(root.left);
    let right = this.preOrderTraversal(root.right);
    return [root.val, ...left, ...right];
  }

  preOrderTraversalV2(root) {
    if (!root) return [];
    let newArray = new Array();
    newArray.push(root.val);
    newArray.push(...this.preOrderTraversalV2(root.left));
    newArray.push(...this.preOrderTraversalV2(root.right));
    return newArray;
  }

  inOrderTraversal(root) {
    if (!root) return [];
    let left = this.inOrderTraversal(root.left);
    let right = this.inOrderTraversal(root.right);
    return [...left, root.val, ...right];
  }

  inOrderTraversalV2(root) {
    if (!root) return [];
    let newArray = new Array();
    newArray.push(...this.inOrderTraversalV2(root.left));
    newArray.push(root.val);
    newArray.push(...this.inOrderTraversalV2(root.right));
    return newArray;
  }

  postOrderTraversal(root) {
    if (!root) return [];
    let left = this.postOrderTraversal(root.left);
    let right = this.postOrderTraversal(root.right);
    return [...left, ...right, root.val];
  }

  postOrderTraversalV2(root) {
    if (!root) return [];
    let newArray = new Array();
    newArray.push(...this.postOrderTraversalV2(root.left));
    newArray.push(...this.postOrderTraversalV2(root.right));
    newArray.push(root.val);
    return newArray;
  }

  // Iterative Depth First Search

  iterativePreOrder(root) {
    let stack = [root];
    let results = [];
    while (stack.length) {
      let current = stack.pop();
      results.push(current);
      if (current.left) stack.push(current.left);
      if (current.right) stack.push(current.right);
    }
    return results;
  }

  iterativeInOrder(root) {
    let stack = [];
    let current = root;
    let results = [];
    while (true) {
      while (current) {
        stack.push(current);
        current = current.left;
      }

      if (!stack.length) break;
      let removed = stack.pop();
      results.push(removed);
      current = current.right;
    }
    return results;
  }

  //To-Do iterativePostOrder

  //Breadth First Search

  breadthFirstSearch(root) {
    let queue = [root];
    let result = [];
    while (queue.length) {
      let current = queue.shift();
      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.left);
      current.push(result);
    }
    return result;
  }

  // Converting a Sorted Array to a Binary Search Tree

  sortedArrayToBST(nums) {
    if (nums.length === 0) return null;

    let mid = Math.floor(nums.length / 2);
    let root = new TreeNode(nums[mid]);

    let left = nums.slice(0, mid);
    root.left = sortedArrayToBST(left);

    let right = nums.slice(mid + 1);
    root.right = sortedArrayToBST(right);

    return root;
  }
}

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  //Insert a new node

  recursiveInsert(val, currentNode = this.root) {
    if (!this.root) {
      this.root = new TreeNode(val);
      return this;
    }
    if (val < currentNode.val) {
      if (!currentNode.left) {
        currentNode.left = new TreeNode(val);
      } else {
        this.insert(val, currentNode.left);
      }
    } else {
      if (!currentNode.right) {
        currentNode.right = new TreeNode(val);
      } else {
        this.insert(val, currentNode.right);
      }
    }
  }

  iterativeInsert(val, currentNode = this.root) {
    if (!this.root) {
      this.root = new TreeNode(val);
      return this;
    }
    if (val < currentNode.val) {
      if (!currentNode.left) {
        currentNode.left = new TreeNode();
      } else {
        while (true) {
          if (val < currentNode.val) {
            if (!currenNodet.left) {
              currentNode.left = new TreeNode();
              return this;
            } else {
              currentNode = currentNode.left;
            }
          } else {
            if (!currentNode.right) {
              currentNode.right = new TreeNode();
              return this;
            } else {
              currentNode = currentNode.right;
            }
          }
        }
      }
    }
  }

  //Search the tree

  searchRecur(val, currentNode = this.root) {
    if (!currentNode) return false;
    if (val < currentNode.val) {
      return this.searchRecur(val, currentNode.left);
    } else if (val > currentNode.val) {
      return this.searchRecur(val, currentNode.right);
    } else {
      return true;
    }
  }

  searchIter(val) {
    let currentNode = this.root;
    while (currentNode) {
      if (val < currentNode.val) {
        currentNode = currentNode.left;
      } else if (val > currentNode.val) {
        currentNode = currentNode.right;
      } else {
        return true;
      }
    }
    return false;
  }

  // Maybe works, who knows, pulled it off the internet....

  deleteNodeHelper(root, key) {
    if (root === null) {
      return false;
    }
    if (key < root.val) {
      root.left = deleteNodeHelper(root.left, key);
      return root;
    } else if (key > root.val) {
      root.right = deleteNodeHelper(root.right, key);
      return root;
    } else {
      if (root.left === null && root.right === null) {
        root = null;
        return root;
      }
      if (root.left === null) return root.right;
      if (root.right === null) return root.left;

      let currNode = root.right;
      while (currNode.left !== null) {
        currNode = currNode.left;
      }
      root.val = currNode.val;
      root.right = deleteNodeHelper(root.right, currNode.val);
      return root;
    }
  }

  //Recursive Depth First Search

  preOrderTraversal(root) {
    if (!root) return [];
    let left = this.preOrderTraversal(root.left);
    let right = this.preOrderTraversal(root.right);
    return [root.val, ...left, ...right];
  }

  preOrderTraversalV2(root) {
    if (!root) return [];
    let newArray = new Array();
    newArray.push(root.val);
    newArray.push(...this.preOrderTraversalV2(root.left));
    newArray.push(...this.preOrderTraversalV2(root.right));
    return newArray;
  }

  inOrderTraversal(root) {
    if (!root) return [];
    let left = this.inOrderTraversal(root.left);
    let right = this.inOrderTraversal(root.right);
    return [...left, root.val, ...right];
  }

  inOrderTraversalV2(root) {
    if (!root) return [];
    let newArray = new Array();
    newArray.push(...this.inOrderTraversalV2(root.left));
    newArray.push(root.val);
    newArray.push(...this.inOrderTraversalV2(root.right));
    return newArray;
  }

  postOrderTraversal(root) {
    if (!root) return [];
    let left = this.postOrderTraversal(root.left);
    let right = this.postOrderTraversal(root.right);
    return [...left, ...right, root.val];
  }

  postOrderTraversalV2(root) {
    if (!root) return [];
    let newArray = new Array();
    newArray.push(...this.postOrderTraversalV2(root.left));
    newArray.push(...this.postOrderTraversalV2(root.right));
    newArray.push(root.val);
    return newArray;
  }

  // Iterative Depth First Search

  iterativePreOrder(root) {
    let stack = [root];
    let results = [];
    while (stack.length) {
      let current = stack.pop();
      results.push(current);
      if (current.left) stack.push(current.left);
      if (current.right) stack.push(current.right);
    }
    return results;
  }

  iterativeInOrder(root) {
    let stack = [];
    let current = root;
    let results = [];
    while (true) {
      while (current) {
        stack.push(current);
        current = current.left;
      }

      if (!stack.length) break;
      let removed = stack.pop();
      results.push(removed);
      current = current.right;
    }
    return results;
  }

  //To-Do iterativePostOrder

  //Breadth First Search

  breadthFirstSearch(root) {
    let queue = [root];
    let result = [];
    while (queue.length) {
      let current = queue.shift();
      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.left);
      current.push(result);
    }
    return result;
  }

  // Converting a Sorted Array to a Binary Search Tree

  sortedArrayToBST(nums) {
    if (nums.length === 0) return null;

    let mid = Math.floor(nums.length / 2);
    let root = new TreeNode(nums[mid]);

    let left = nums.slice(0, mid);
    root.left = sortedArrayToBST(left);

    let right = nums.slice(mid + 1);
    root.right = sortedArrayToBST(right);

    return root;
  }
}

Binary Search Tree

hashtagPros of a BST

hashtagCons of a BST

hashtagImplementing a BST in Python

hashtagStep 1 – BSTNode Class

hashtagStep 2 – Insert

hashtagStep 3 – Get Min and Get Max

hashtagStep 4 – Delete

hashtagStep 5 – Exists

hashtagStep 6 – Inorder

hashtagStep 7 – Preorder

hashtagStep 8 – Postorder

hashtagUsing the BST

hashtagFull Binary Search Tree in Python

hashtagWhere would you use a binary search tree in real life?

hashtagExample Binary Tree

hashtagVisual Aid

hashtag

hashtagExample Code

hashtagTerms

hashtagSearch Patterns

hashtagConstraints

hashtagPseudoCode For Insertion

hashtagPseudoCode For Search Of A single Item

hashtagPseudoCode For Breadth First Search Traversal

hashtagPseudoCode For Depth First Search Traversal

hashtagPre-Order

hashtagIn-Order

hashtagPost-Order

hashtagExample Binary Search Tree

BST Explained

hashtagWhat is a Binary Search Tree?

BST Insert

BST-Largest-Sub-Tree

BST Insert

BST-Largest-Sub-Tree

BST Explained

hashtagWhat is a Binary Search Tree?

hashtagOperations in Binary Search Tree

hashtagCreate Tree Class

Binary Search Tree

hashtagPros of a BST

hashtagCons of a BST

hashtagImplementing a BST in Python

hashtagStep 1 – BSTNode Class

hashtagStep 2 – Insert

hashtagStep 3 – Get Min and Get Max

hashtagStep 4 – Delete

hashtagStep 5 – Exists

hashtagStep 6 – Inorder

hashtagStep 7 – Preorder

hashtagStep 8 – Postorder

hashtagUsing the BST

hashtagFull Binary Search Tree in Python

hashtagWhere would you use a binary search tree in real life?

hashtagExample Binary Tree

hashtagVisual Aid

hashtag

hashtagExample Code

hashtagTerms

hashtagSearch Patterns

hashtagConstraints

hashtagPseudoCode For Insertion

hashtagPseudoCode For Search Of A single Item

hashtagPseudoCode For Breadth First Search Traversal

hashtagPseudoCode For Depth First Search Traversal

hashtagPre-Order

hashtagIn-Order

hashtagPost-Order

hashtagExample Binary Search Tree

Pros of a BST

Cons of a BST

Implementing a BST in Python

Step 1 – BSTNode Class

Step 2 – Insert

Step 3 – Get Min and Get Max

Step 4 – Delete

Step 5 – Exists

Step 6 – Inorder

Step 7 – Preorder

Step 8 – Postorder

Using the BST

Full Binary Search Tree in Python

Where would you use a binary search tree in real life?

Example Binary Tree

Visual Aid

Example Code

Terms

Search Patterns

Constraints

PseudoCode For Insertion

PseudoCode For Search Of A single Item

PseudoCode For Breadth First Search Traversal

PseudoCode For Depth First Search Traversal

Pre-Order

In-Order

Post-Order

Example Binary Search Tree

What is a Binary Search Tree?

What is a Binary Search Tree?

Operations in Binary Search Tree

Create Tree Class

Pros of a BST

Cons of a BST

Implementing a BST in Python

Step 1 – BSTNode Class

Step 2 – Insert

Step 3 – Get Min and Get Max

Step 4 – Delete

Step 5 – Exists

Step 6 – Inorder

Step 7 – Preorder

Step 8 – Postorder

Using the BST

Full Binary Search Tree in Python

Where would you use a binary search tree in real life?

Example Binary Tree

Visual Aid

Example Code

Terms

Search Patterns

Constraints

PseudoCode For Insertion

PseudoCode For Search Of A single Item

PseudoCode For Breadth First Search Traversal

PseudoCode For Depth First Search Traversal

Pre-Order

In-Order

Post-Order

Example Binary Search Tree