JAVA

binary search tree in c++

// C++ program to demonstrate insertion
// in a BST recursively.
#include <iostream>
using namespace std;
 
class BST {
    int data;
    BST *left, *right;
 
public:
    // Default constructor.
    BST();
 
    // Parameterized constructor.
    BST(int);
 
    // Insert function.
    BST* Insert(BST*, int);
 
    // Inorder traversal.
    void Inorder(BST*);
};
 
// Default Constructor definition.
BST ::BST()
    : data(0)
    , left(NULL)
    , right(NULL)
{
}
 
// Parameterized Constructor definition.
BST ::BST(int value)
{
    data = value;
    left = right = NULL;
}
 
// Insert function definition.
BST* BST ::Insert(BST* root, int value)
{
    if (!root) {
        // Insert the first node, if root is NULL.
        return new BST(value);
    }
 
    // Insert data.
    if (value > root->data) {
        // Insert right node data, if the 'value'
        // to be inserted is greater than 'root' node data.
 
        // Process right nodes.
        root->right = Insert(root->right, value);
    }
    else if (value < root->data){
        // Insert left node data, if the 'value'
        // to be inserted is smaller than 'root' node data.
 
        // Process left nodes.
        root->left = Insert(root->left, value);
    }
 
    // Return 'root' node, after insertion.
    return root;
}
 
// Inorder traversal function.
// This gives data in sorted order.
void BST ::Inorder(BST* root)
{
    if (!root) {
        return;
    }
    Inorder(root->left);
    cout << root->data << endl;
    Inorder(root->right);
}

Binary Search Tree

"""Binary Search Tree

Included:
	- Insert
    - Find data/ minimum/ maximum
    - Size
    - Height
    - Traversals (Inorder, preorder, postorder)
    - Test Code for it
    
Not included:
	- Delete
    - Display (as 2D BST)
	and others...
"""

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # Insert a node
    def put(self, data):
        if self.root is None: # BST empty
            self.root = Node(data)
        else:
            curr = self.root # initialise curr pointer
            while curr:
                if data < curr.data: # data put at left
                    if curr.left:
                        curr = curr.left
                    else: # no left child
                        curr.left = Node(data)
                        break
                else: # data put at right
                    if curr.right:
                        curr = curr.right
                    else:  # no right child
                        curr.right = Node(data)
                        break   
                        
    def find(self, data):
        curr = self.root   # start from root
        while curr:
            if data < curr.data:  # data at left
                curr = curr.left
            elif data > curr.data:    # data at right
                curr = curr.right
            else:
                return True # found
        return False
    
    def min_of(self):
        curr = self.root # start from root
        while curr.left:
            curr = curr.left # keep going left
        return curr.data
        
    def max_of(self):
        curr = self.root # start from root
        while curr.right:
            curr = curr.right # keep going right
        return curr.data
    
    def size(self):
        def go(node): # helper
            if node:
                return 1 + go(node.left) + go(node.right)
            return 0
        return go(self.root)   
    
    def height(self):
        def go(node): # helper
            if node:
                return 1 + max(go(node.left), go(node.right))
            return -1 # it has -1 if empty
        return go(self.root)

        
    # In_order
    def in_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                go(node.left) # left
                lst.append(node.data) # Node
                go(node.right) # Right
        go(self.root)
        return lst
    
    # Pre_order
    def pre_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                lst.append(node.data) # Node
                go(node.left) # left
                go(node.right) # Right
        go(self.root)
        return lst
    
    # Post_order
    def post_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                go(node.left) # left
                go(node.right) # Right
                lst.append(node.data) # Node
        go(self.root)
        return lst

# Test
from random import randint, sample
def BST_tester(BST):
    r = randint(5, 10)
    lst = [randint(10, 100) for _ in range(r)]
    print(f"List: {lst}", 
          f"Sorted: {sorted(lst)}",
          sep = "
", end = "

")
    
    B = BST()
    for item in lst:
        B.put(item)
    lst.sort()
    print("AFTER INSERTION:",
          f"Size: {B.size()} | {B.size() == len(lst)}",
          f"Height: {B.height()} | I can't code the display for this",
          f"Min: {B.min_()} | {B.min_() == min(lst)}",
          f"Max: {B.max_()} | {B.max_() == max(lst)}",
          sep = "
", end = "

")
    
    items = sample(lst, 5) + [randint(10, 100) for _ in range(5)] # 5 confirm in list, 5 might be in list
    found = [B.find(_) for _ in items]
    zipped = list(zip(items, found))
    inlst, notinlst = zipped[:5], zipped[5:] 
    print(f"Sampled from lst: {inlst} | All True: {all(found[:5])}",
          f"Random: {notinlst}",
          sep = "
", end = "

")
    
    print(f"Inord: {B.in_ord()} | Correct Insertion: {lst == B.in_ord()}",
          f"Preord: {B.pre_ord()}",
          f"Postord: {B.post_ord()}",
          sep = "
")
BST_tester(BST)

binary search tree

# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
            তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root  নোডের  পরিবর্তন ঘটবে।
            এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none), 
                then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change. 
                This is why we return to the root node.
'''
# 1st system:

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

    def __repr__(self):
        return repr(self.data)

    def add_left(self, node):
        self.left = node
        if node is not None:
            node.parent = self

    def add_right(self, node):
        self.right = node
        node.parent = self

# now bst_insert:
def bst_insert(root,node):
    last_node = None
    current_node = root
    while current_node is not None:
        last_node = current_node
        if node.data < current_node.data:
            current_node = current_node.left
        else:
            current_node = current_node.right
    if last_node is None:
        # tree was empty. node is the only node, hence root
        root = node # new node add
    elif node.data < last_node.data:
        last_node.add_left(node)
    else:
        last_node.add_right(node)
    return root
'''
              _10_
             /    
            5      17
           /      /  
          3      12  19
         /              
        1   4         
   
'''
# now create_bst:
def create_bst():
    li = list(map(int,input().split()))
    root = TreeNode(li)
    for item in root:
        node = TreeNode(item)
        root = bst_insert(root, node)
    return root

# In_order tree traverse:
def in_order(node):
    if node.left:
        in_order(node.left)
    print(node)
    if node.right:
        in_order(node.right)

# bst- tree minimum node:
def bst_minimum(root):
    while root.left is not None:
        root = root.left
    print(root)

# bst_tree maximum node:
def bst_maximum(root):
    while root.right is not None:
        root = root.right
    print(root)


# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
    while node is not None:
        if node.data == key:
            return node
        if key < node.data:
            node = node.left
        else:
            node = node.right
    return node

# Now check to your code:
if __name__ == "__main__":
    root = create_bst()
    print("Tree is root =",root)
    print()
    # In_order tree traverse:
    print("In_order Tree:")
    in_order(root)
    print()

    # bst- tree minimum node:
    print("Minimum node:")
    bst_minimum(root)
    print()

    # bst_tree maximum node:
    print("Maximum node:")
    bst_maximum(root)
    print()

    # input with searching:
    print("bst_search:")
    for key in [int(input("Please Enter the search key: ")),int(input("Please Enter the search key: "))]:
        print("Searching =",key)
        result = best_search(root, key)
        print("Result =",result)

Binary Search Tree

# Tree traversal in Python


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


def inorder(root):

    if root:
        # Traverse left
        inorder(root.left)
        # Traverse root
        print(str(root.val) + "->", end='')
        # Traverse right
        inorder(root.right)


def postorder(root):

    if root:
        # Traverse left
        postorder(root.left)
        # Traverse right
        postorder(root.right)
        # Traverse root
        print(str(root.val) + "->", end='')


def preorder(root):

    if root:
        # Traverse root
        print(str(root.val) + "->", end='')
        # Traverse left
        preorder(root.left)
        # Traverse right
        preorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Inorder traversal ")
inorder(root)

print("
Preorder traversal ")
preorder(root)

print("
Postorder traversal ")
postorder(root)

binary search tree

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.

binary search tree

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.

binary search tree

# Driver Code 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print ("Element is present at index % d" % result) 
else: 
    print ("Element is not present in array")

Binary Search Tree

A binary tree is said to be a binary search tree if for every node, the left is smaller than it and the right is bigger than it. 

Example
       10
    9      20
  6  11   13  26

For example, try looking for 13 and 26.
13 is larger than 10, so go to the right.
13 is smaller than 20, so go to the left.

26 is larger than 10, so go to the right.
26 is larger than 20, so go to the right.
   

binary search tree

// Java program to demonstrate
// insert operation in binary
// search tree
class BinarySearchTree {
 
    /* Class containing left
       and right child of current node
     * and key value*/
    class Node {
        int key;
        Node left, right;
 
        public Node(int item)
        {
            key = item;
            left = right = null;
        }
    }
 
    // Root of BST
    Node root;
 
    // Constructor
    BinarySearchTree() { root = null; }
 
    BinarySearchTree(int value) { root = new Node(value); }
 
    // This method mainly calls insertRec()
    void insert(int key) { root = insertRec(root, key); }
 
    /* A recursive function to
       insert a new key in BST */
    Node insertRec(Node root, int key)
    {
 
        /* If the tree is empty,
           return a new node */
        if (root == null) {
            root = new Node(key);
            return root;
        }
 
        /* Otherwise, recur down the tree */
        else if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
 
        /* return the (unchanged) node pointer */
        return root;
    }
 
    // This method mainly calls InorderRec()
    void inorder() { inorderRec(root); }
 
    // A utility function to
    // do inorder traversal of BST
    void inorderRec(Node root)
    {
        if (root != null) {
            inorderRec(root.left);
            System.out.println(root.key);
            inorderRec(root.right);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
 
        /* Let us create following BST
              50
           /     
          30      70
         /      /  
       20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
 
        // print inorder traversal of the BST
        tree.inorder();
    }
}
// This code is contributed by Ankur Narain Verma

tree search

const isPresent = (target , root)=>{
  if (root === null) return null;
  const result = [];
  const queue = [root];


  while (queue.length > 0) {
    const current = queue.shift();
    if(target===current.data){
      return true
    }
    result.push(current.data);
    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }
  return false;

}

tree search

// search for target in  a tree using recursive function  
const treeIncludes = (target , root )=>{

if(root===null)return false;
if(root.data===target) return true ;
return treeIncludes(target , root.left ) || treeIncludes(target , root.right );

}

Binary Search Tree

//Java Binary Search Tree with In-Order, Pre-Order and Post-Order Traversals
public class BinarySearchTree {
    public static void main(String[] args) {
        searchSolution s = new searchSolution();

        s.insertionkey('J');
        s.insertionkey('B');
        s.insertionkey('E');
        s.insertionkey('C');
        s.insertionkey('G');
        s.insertionkey('A');
        s.insertionkey('H');
        s.insertionkey('I');
        s.insertionkey('D');
        s.insertionkey('F');

        System.out.println("IN ORDER Search");
        s.InOrderTraversal(s.root);
        System.out.println();
        System.out.println();

        System.out.println("PRE ORDER Search");
        s.PreOrderTraversal(s.root);
        System.out.println();
        System.out.println();

        System.out.println("POST ORDER Search");
        s.PostOrderTraversal(s.root);
    }

}

class searchSolution {
    node root;

    void insertionkey(char key) {
        root = insertionInTree(root, key);
    }

    node insertionInTree(node root, char key) {
        if (root == null) {
            root = new node(key);
            return root;
        }

        if (key < root.key) {
            root.left = insertionInTree(root.left, key);
        } else if (key > root.key) {
            root.right = insertionInTree(root.right, key);
        }
        return root;
    }

    void InOrderTraversal(node n) {
        // InOrder Traversal = Left Root Right
        if (n != null) {
            InOrderTraversal(n.left);
            System.out.print(n.key + " ");
            InOrderTraversal(n.right);
        }
    }

    void PreOrderTraversal(node n) {
        // PreOrder Traversal = Root Left Right
        if (n != null) {
            System.out.print(n.key + " ");
            PreOrderTraversal(n.left);
            PreOrderTraversal(n.right);
        }
    }

    void PostOrderTraversal(node n) {
        // PostOrder Traversal = Left Right Root
        if (n != null) {
            PostOrderTraversal(n.left);
            PostOrderTraversal(n.right);
            System.out.print(n.key + " ");
        }
    }
}

class node { 
    char key;
    node left, right;

    node(char KEY) {
        this.key = KEY;
    }
}

binary search tree

# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
            তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root  নোডের  পরিবর্তন ঘটবে।
            এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none), 
                then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change. 
                This is why we return to the root node.
'''

# second system:

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

    def __repr__(self):
        return repr(self.data)

    def add_left(self, node):
        self.left = node
        if node is not None:
            node.parent = self

    def add_right(self, node):
        self.right = node
        node.parent = self

# now bst_insert:
def bst_insert(root,node):
    last_node = None
    current_node = root
    while current_node is not None:
        last_node = current_node
        if node.data < current_node.data:
            current_node = current_node.left
        else:
            current_node = current_node.right
    if last_node is None:
        # tree was empty. node is the only node, hence root
        root = node # new node add
    elif node.data < last_node.data:
        last_node.add_left(node)
    else:
        last_node.add_right(node)
    return root
'''
              _10_
             /    
            5      17
           /      /  
          3      12  19
         /              
        1   4         
   
'''
# now create_bst:
def create_bst():
    root = TreeNode(10)
    for item in [5,17,3,7,12,19,1,4]:
        node = TreeNode(item)
        root = bst_insert(root, node)
    return root

# In_order tree traverse:
def in_order(node):
    if node.left:
        in_order(node.left)
    print(node)
    if node.right:
        in_order(node.right)

# bst- tree minimum node:
def bst_minimum(root):
    while root.left is not None:
        root = root.left
    print(root)

# Node transfer:
def bst_transfer(root, current_node, new_node):
    if current_node.parent is None:
        root = new_node
    elif current_node == current_node.parent.left:
        current_node.parent.add_left(new_node)
    else:
        current_node.parent.add_right(new_node)
    return root

# Node delete:
def bst_delete(root,node):
    if node.left is None:
        root = bst_transfer(root,node,node.right)
    elif node.right is None:
        root = bst_transfer(root,node,node.left)

    else:
        min_node = bst_minimum(node.right)
        if min_node.parent != node:
            root = bst_transfer(root,min_node,min_node.right)
            min_node.add_right(node.right)
        root = bst_transfer(root,node,min_node)
        min_node.add_left(node.left)
    return root



# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
    while node is not None:
        if node.data == key:
            return node
        if key < node.data:
            node = node.left
        else:
            node = node.right
    return node

# Now check to your code:
if __name__ == "__main__":
    root = create_bst()
    print("Tree is root =",root)
    print()

    print("BST:")
    in_order(root)

    for key in [1,5,10]:
        node = best_search(root,key)
        print("will delete =", node)
        root = bst_delete(root,node)
        print("BST:")
        in_order(root)