You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

4.7 KiB

In [1]:
"""Python3 program to demonstrate insert
operation in binary search tree """

# A Binary Tree Node
# Utility function to create a
# new tree node
class newNode:

    # Constructor to create a newNode
    def __init__(self, data):
        self.key= data
        self.left = None
        self.right = self.parent = None

# A utility function to insert a new
# Node with given key in BST
def insert(root, key):

    # Create a new Node containing
    # the new element
    newnode = newNode(key)

    # Pointer to start traversing from root
    # and traverses downward path to search
    # where the new node to be inserted
    x = root

    # Pointer y maintains the trailing
    # pointer of x
    y = None

    while (x != None):
        y = x
        if (key < x.key):
            x = x.left
        else:
            x = x.right
    
    # If the root is None i.e the tree is
    # empty. The new node is the root node
    if (y == None):
        y = newnode

    # If the new key is less then the leaf node key
    # Assign the new node to be its left child
    elif (key < y.key):
        y.left = newnode

    # else assign the new node its
    # right child
    else:
        y.right = newnode

    # Returns the pointer where the
    # new node is inserted
    return y

# A utility function to do inorder
# traversal of BST
def Inorder(root) :

    if (root == None) :
        return
    else:
        Inorder(root.left)
        print( root.key, end = " " )
        Inorder(root.right)

#Driver Code
if __name__ == '__main__':

    root = None
    root = insert(root, "m")
    insert(root, "n")
    insert(root, "l")
    insert(root, "p")
    insert(root, "q")
    insert(root, "a")
    insert(root, "b")


    # Pr inorder traversal of the BST


# This code is contributed by
# SHUBHAMSINGH10
In [3]:
# print binary tree in 2D copied from sample program
COUNT = [10]
def print2DUtil(root, space) :

    # Base case
    if (root == None) :
        return

    # Increase distance between levels
    space += COUNT[0]

    # Process right child first
    print2DUtil(root.right, space)

    # Print current node after space
    # count
    print()
    for i in range(COUNT[0], space):
        print(end = " ")
    print(root.key)

    # Process left child
    print2DUtil(root.left, space)

# Wrapper over print2DUtil()
def print2D(root) :
    
    # space=[0]
    # Pass initial space count as 0
    print2DUtil(root, 0)

# Driver Code
if __name__ == '__main__':

    
    print2D(root)
                              q

                    p

          n

m

          l

                              b

                    a