Binary search tree insert recursive python

The problem is that a node may be None and you're calling a function with it, and then assigning a node to None and nothing gets saved.

Let's have a look:

def insert(self, root, value):  # say root is None
    if root is None:
        root = Node(value)  # here we're doing: `None = Node(value)`
    else:
        if value < root.value:
            root.left = self.insert(root.left, value)
        else:
            root.right = self.insert(root.right, value)
    return root 

In order to fix it we need to "go one level up" and if node.left is None then do the assignment to node.left (root is a bad name by the way, so I'm using "node" instead).

One way to do it would be:

def insert(self, value):  # this is the function that gets called, pay attention that we're not sending `root`
    if self.root is None:
        self.root = Node(value)
    else:
        self._insert(self.root, value) # here's the call to a "private" function to which we are passing nodes down, starting from root

def _insert(self, node, value):
    if value < node.value:  # we know that `node` cannot be None - so it's safe to check its value! 
        if node.left:
            self._insert(node.left, value) # the recursive call is done only when `node.left` is not None
        else:
            node.left = Node(value)  # direct assignment
    else:
        if node.right:
            self._insert(node.right, value)
        else:
            node.right = Node(value)  # direct assignment

Two comments:

1. Now there's a cleaner interface, see how insert calls look now:

    bst = BinaryTree()
    bst.insert(2)
    bst.insert(4)
    bst.insert(3)
    bst.insert(1)

1. insert is an action that "sets" a value, and as such - it does not have to return anything (it can though, if you really want it to).

What is Binary Search Tree?

A 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.

How to search a key in given Binary Tree?

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, in binary search, 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 middle element (median) of the search space and if the record being searched is less than the middle element, 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 if the mid element is not the element that we are looking for, we reduce the search space to ‘n/2’ we keep reducing the search space until 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 operations in binary search trees will be very similar. Let’s say we want to search for the number, we start at the root, and then we 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 smaller 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 smaller and all the elements in the right subtree are larger. Searching an element in the binary search tree is basically this traversal, at each step we go either left or right and 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 start with a search space of ‘n’ nodes and as we discard one of the sub-trees, we discard ‘n/2’ nodes so our search space gets reduced to ‘n/2’. In the next step, we reduce the search space to ‘n/4’ and we repeat until we find the element or our search space is reduced to only one node. The search here is also a binary search hence the name; Binary Search Tree.

Implementation:

C++

struct node* search(struct node* root, int key)

{

    if (root == NULL || root->key == key)

       return root;

    if (root->key < key)

       return search(root->right, key);

    return search(root->left, key);

}

Java

public Node search(Node root, int key)

{

    if (root==null || root.key==key)

        return root;

    if (root.key < key)

       return search(root.right, key);

    return search(root.left, key);

}

Python

def search(root,key):

    if root is None or root.val == key:

        return root

    if root.val < key:

        return search(root.right,key)

    return search(root.left,key)

C#

public Node search(Node root,

                   int key)

{

    if (root == null ||

        root.key == key)

        return root;

    if (root.key < key)

       return search(root.right, key);

    return search(root.left, key);

}

Javascript

Illustration to search 6 in below tree: 

1. Start from the root. 
2. Compare the searching element with root, if less than root, then recursively call left subtree, else recursively call right subtree. 
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 for 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. 

         100                               100

        /   \        Insert 40            /    \

      20     500    ———>          20     500 

     /  \                              /  \  

    10   30                           10   30

                                              \   

                                              40

Implementation:

C++

#include

using namespace std;

class BST {

    int data;

    BST *left, *right;

public:

    BST();

    BST(int);

    BST* Insert(BST*, int);

    void Inorder(BST*);

};

BST ::BST()

    : data(0)

    , left(NULL)

    , right(NULL)

{

}

BST ::BST(int value)

{

    data = value;

    left = right = NULL;

}

BST* BST ::Insert(BST* root, int value)

{

    if (!root) {

        return new BST(value);

    }

    if (value > root->data) {

        root->right = Insert(root->right, value);

    }

    else if (value < root->data){

        root->left = Insert(root->left, value);

    }

    return root;

}

void BST ::Inorder(BST* root)

{

    if (!root) {

        return;

    }

    Inorder(root->left);

    cout << root->data << endl;

    Inorder(root->right);

}

int main()

{

    BST b, *root = NULL;

    root = b.Insert(root, 50);

    b.Insert(root, 30);

    b.Insert(root, 20);

    b.Insert(root, 40);

    b.Insert(root, 70);

    b.Insert(root, 60);

    b.Insert(root, 80);

    b.Inorder(root);

    return 0;

}

C

#include

#include

struct node {

    int key;

    struct node *left, *right;

};

struct node* newNode(int item)

{

    struct node* temp

        = (struct node*)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

void inorder(struct node* root)

{

    if (root != NULL) {

        inorder(root->left);

        printf("%d \n", root->key);

        inorder(root->right);

    }

}

struct node* insert(struct node* node, int key)

{

    if (node == NULL)

        return newNode(key);

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

    return node;

}

int main()

{

    struct node* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

    inorder(root);

    return 0;

}

Java

class BinarySearchTree {

    class Node {

        int key;

        Node left, right;

        public Node(int item)

        {

            key = item;

            left = right = null;

        }

    }

    Node root;

    BinarySearchTree() { root = null; }

    BinarySearchTree(int value) { root = new Node(value); }

    void insert(int key) { root = insertRec(root, key); }

    Node insertRec(Node root, int key)

    {

        if (root == null) {

            root = new Node(key);

            return root;

        }

        else if (key < root.key)

            root.left = insertRec(root.left, key);

        else if (key > root.key)

            root.right = insertRec(root.right, key);

        return root;

    }

    void inorder() { inorderRec(root); }

    void inorderRec(Node root)

    {

        if (root != null) {

            inorderRec(root.left);

            System.out.println(root.key);

            inorderRec(root.right);

        }

    }

    public static void main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

        tree.inorder();

    }

}

Python

class Node:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

def insert(root, key):

    if root is None:

        return Node(key)

    else:

        if root.val == key:

            return root

        elif root.val < key:

            root.right = insert(root.right, key)

        else:

            root.left = insert(root.left, key)

    return root

def inorder(root):

    if root:

        inorder(root.left)

        print(root.val)

        inorder(root.right)

r = Node(50)

r = insert(r, 30)

r = insert(r, 20)

r = insert(r, 40)

r = insert(r, 70)

r = insert(r, 60)

r = insert(r, 80)

inorder(r)

C#

using System;

class BinarySearchTree {

    public class Node {

        public int key;

        public Node left, right;

        public Node(int item)

        {

            key = item;

            left = right = null;

        }

    }

    Node root;

    BinarySearchTree() { root = null; }

    BinarySearchTree(int value) { root = new Node(value); }

    void insert(int key) { root = insertRec(root, key); }

    Node insertRec(Node root, int key)

    {

        if (root == null) {

            root = new Node(key);

            return root;

        }

        if (key < root.key)

            root.left = insertRec(root.left, key);

        else if (key > root.key)

            root.right = insertRec(root.right, key);

        return root;

    }

    void inorder() { inorderRec(root); }

    void inorderRec(Node root)

    {

        if (root != null) {

            inorderRec(root.left);

            Console.WriteLine(root.key);

            inorderRec(root.right);

        }

    }

    public static void Main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

        tree.inorder();

    }

}

Javascript

Output

20
30
40
50
60
70
80

Illustration to insert 2 in below tree: 

1.  Start from the root. 
2. Compare the inserting element with root, if less than root, then recursively call left subtree, else recursively call right subtree. 
3. After reaching the end, just insert that node at left(if less than current) or 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). 

Implementation: Insertion using loop.

C++

#include

using namespace std;

class Node {

public:

    int val;

    Node* left;

    Node* right;

    Node(int val)

        : val(val)

        , left(NULL)

        , right(NULL)

    {

    }

};

void insert(Node*& root, int key)

{

    Node* node = new Node(key);

    if (!root) {

        root = node;

        return;

    }

    Node* prev = NULL;

    Node* temp = root;

    while (temp) {

        if (temp->val > key) {

            prev = temp;

            temp = temp->left;

        }

        else if (temp->val < key) {

            prev = temp;

            temp = temp->right;

        }

    }

    if (prev->val > key)

        prev->left = node;

    else

        prev->right = node;

}

void inorder(Node* root)

{

    Node* temp = root;

    stack st;

    while (temp != NULL || !st.empty()) {

        if (temp != NULL) {

            st.push(temp);

            temp = temp->left;

        }

        else {

            temp = st.top();

            st.pop();

            cout << temp->val << " ";

            temp = temp->right;

        }

    }

}

int main()

{

    Node* root = NULL;

    insert(root, 30);

    insert(root, 50);

    insert(root, 15);

    insert(root, 20);

    insert(root, 10);

    insert(root, 40);

    insert(root, 60);

    inorder(root);

    return 0;

}

Java

import java.util.*;

import java.io.*;

class GFG {

    public static void main (String[] args) {

         BST tree=new BST();

        tree.insert(30);

        tree.insert(50);

        tree.insert(15);

        tree.insert(20);

        tree.insert(10);

        tree.insert(40);

        tree.insert(60);

        tree.inorder();

    }

}

class Node{

    Node left;

    int val;

    Node right;

    Node(int val){

        this.val=val;

    }

}

class BST{

  Node root;

  public void insert(int key){

        Node node=new Node(key);

        if(root==null) {

            root = node;

            return;

        }

        Node prev=null;

        Node temp=root;

        while (temp!=null){

            if(temp.val>key){

                prev=temp;

                temp=temp.left;

            }

            else if (temp.val

                prev=temp;

                temp=temp.right;

            }

        }

        if(prev.val>key)

            prev.left=node;

        else prev.right=node;

    }

   public void inorder(){

        Node temp=root;

        Stack stack=new Stack<>();

        while (temp!=null||!stack.isEmpty()){

            if(temp!=null){

                stack.add(temp);

                temp=temp.left;

            }

            else {

                temp=stack.pop();

                System.out.print(temp.val+" ");

                temp=temp.right;

            }

        }

    }

}

Python3

class GFG :

    @staticmethod

    def main( args) :

        tree = BST()

        tree.insert(30)

        tree.insert(50)

        tree.insert(15)

        tree.insert(20)

        tree.insert(10)

        tree.insert(40)

        tree.insert(60)

        tree.inorder()

class Node :

    left = None

    val = 0

    right = None

    def __init__(self, val) :

10 15 20 30 40 50 60